题目描述

吉丽 (JRY) 的电脑里有一份时间表，表上有 $n$ 个时间段，每个时间段吉丽都要和一个妹子约会。每个妹子都有一个属性 $a_i$，表示吉丽和第 $i$ 个妹子约会至少需要带的 $money$。吉丽特意把 $a_i$ 标在了第 $i$ 行，以作备忘。

你听说了吉丽的这张时间表，决定篡改一下数据，让吉丽花更多的 $money$。当然，你对这 $n$ 个妹子也有不同的好感度，所以你准备把第 $i$ 行的数改为 $b_i$。

有一天你趁机接触到了吉丽的时间表，可是时间紧迫，你最多只能输入两个数据，其他只能通过复制得到了。

定义“一次操作”为：修改第i行的数据，将 $a_i$ 改为 $b_i$，选中这个数向上或向下拖动到第 $j$ 行，这样就使得第 $\min(i,j)$ 至第 $\max(i,j)$ 行的数都被覆盖成了 $b_i$。

注意：为了提高效率，你不会修改或覆盖同一行两次以上（包括两次）。

你的时间只够你完成两次操作，你在这么短的时间内仍不忘让吉丽花的 $money$ 越多越好。请你回答：在最多操作两次的情况下，吉丽最多要花多少 $money$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个数，表示 $a_i$。

第三行 $n$ 个数，表示bi。

输出格式

一个数，表示吉丽最多要花的 $money$。

7
1 3 4 7 6 1 2
1 1 3 1 5 1 1

31

样例说明

第一次操作：修改第 $3$ 行，向上拖动到第 $1$ 行。

第二次操作：修改第 $5$ 行，向下拖动到第 $7$ 行。

修改后的数列：$3$ $3$ $3$ $7$ $5$ $5$ $5$，$money$ 和为 $31$，可以验证这是最大值。

数据范围

$1\leq n \leq 500000, 1\leq a_i,b_i, \leq 10^9$

提示

数据已加强，By evil 佂菡

题目来源

XXY杯省选模拟题