题目描述

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

输入

3
2 5 7 4 2 1

输出

8

样例 2

输入

3
8 0 6 0 9 0

输出

12

样例 3

输入

5
3 1 5 7 0 8 4 6 4 9

输出

12

样例 4

输入

1
267503 601617

输出

869120

样例 5

输入

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

输出

513119404