有 $n$ 只熊猫，编号从 $1$ 到 $n$，第 $i$ 只熊猫拥有 $a_i$ 个甜甜圈。同时有 $n$ 个箱子，编号从 $1$ 到 $n$，第 $i$ 个箱子可以容纳 $b_i$ 个甜甜圈。对于任意 $i$（$1 \le i \le n$），第 $i$ 只熊猫可以将他的甜甜圈分发到第 $i$ 个箱子和第 $(i \pmod n + 1)$ 个箱子中。

你能找到一种方法来最大化分发出去的甜甜圈总数吗？

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$（$3 \le n \le 10^6$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）。 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$0 \le b_i \le 10^9$）。

保证所有 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一个整数，表示可以分发出去的甜甜圈的最大总数。

样例

样例输入 1

5
8 4 8 3 10
1 0 4 5 1
5
9 4 10 0 4
3 5 2 2 1

样例输出 1

11
13