题目描述

AtCoder 先生为自己的 $2N$ 个朋友做了一个圆形蛋糕，然后将蛋糕沿中心平均的分成了 $2N$ 块。这些蛋糕块沿顺时针用 $0$ 到 $2N-1$ 编号。

他最后决定放一些草莓润色蛋糕，而他知道朋友们想要多少草莓。具体的来说，$2N$ 个朋友也有自己的编号，一样的从 $0$ 到 $2N-1$。而编号为 $i$ 的朋友希望编号 $i$ 到编号 $i+N-1$ 的所有蛋糕的草莓总数至少为 $A_i$。其中编号为 $x$ 且 $x\geq 2N$ 的蛋糕的编号实际上是 $x-2N$ 。

为了满足所有朋友的需求，AtCoder 先生需要放多少草莓？

输入格式

第一行一个整数 $N$，第二行 $2N$ 个整数 $A_0,A_1,\dots,A_{2N-1}$。

其含义已在题意中解释。

输出格式

一行一个整数表示所需草莓数量的最小值。

输入输出样例 #1

输入 #1

3
2 5 7 4 2 1

输出 #1

8

输入输出样例 #2

输入 #2

3
8 0 6 0 9 0

输出 #2

12

输入输出样例 #3

输入 #3

5
3 1 5 7 0 8 4 6 4 9

输出 #3

12

输入输出样例 #4

输入 #4

1
267503 601617

输出 #4

869120

输入输出样例 #5

输入 #5

8
418940906 38034755 396064111 43044067 356084286 61548818 15301658 35906016 20933120 211233791 30314875 25149642 42550552 104690843 81256233 63578117

输出 #5

513119404