AT_arc117_f [ARC117F] Gateau

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\ \leq\ N\ \leq\ 150000 $ - $ 0\ \leq\ A_i\ \leq\ 5\ \times\ 10^8\ (0\ \leq\ i\ \leq\ 2N-1) $ - 入力はすべて整数 ### Sample Explanation 1 ピース $ 0,\ 1,\ 2,\ 3,\ 4,\ 5 $ の上に置くいちごの個数を、それぞれ $ 1,\ 0,\ 1,\ 4,\ 2,\ 0 $ とする場合を考えます。 そのとき、それぞれの友人の希望は、以下のようにすべて叶います。 - 友人 $ 0 $：ピース $ 0,\ 1,\ 2 $ にはいちごが合計 $ 2 $ 個あり、これは $ A_0\ =\ 2 $ 個以上である - 友人 $ 1 $：ピース $ 1,\ 2,\ 3 $ にはいちごが合計 $ 5 $ 個あり、これは $ A_1\ =\ 5 $ 個以上である - 友人 $ 2 $：ピース $ 2,\ 3,\ 4 $ にはいちごが合計 $ 7 $ 個あり、これは $ A_2\ =\ 7 $ 個以上である - 友人 $ 3 $：ピース $ 3,\ 4,\ 5 $ にはいちごが合計 $ 6 $ 個あり、これは $ A_3\ =\ 4 $ 個以上である - 友人 $ 4 $：ピース $ 4,\ 5,\ 0 $ にはいちごが合計 $ 3 $ 個あり、これは $ A_4\ =\ 2 $ 個以上である - 友人 $ 5 $：ピース $ 5,\ 0,\ 1 $ にはいちごが合計 $ 1 $ 個あり、これは $ A_5\ =\ 1 $ 個以上である したがって、チョコレートケーキ全体で $ 8 $ 個のいちごを置くことで、友人全員の希望を叶えることができます。 これが最小値となります。 ### Sample Explanation 2 ピース $ 0,\ 1,\ 2,\ 3,\ 4,\ 5 $ の上に置くいちごの個数を、それぞれ $ 6,\ 0,\ 2,\ 1,\ 3,\ 0 $ とする場合を考えます。 そのとき、それぞれの友人の希望は、以下のようにすべて叶います。 - 友人 $ 0 $：ピース $ 0,\ 1,\ 2 $ にはいちごが合計 $ 8 $ 個あり、これは $ A_0\ =\ 8 $ 個以上である - 友人 $ 1 $：ピース $ 1,\ 2,\ 3 $ にはいちごが合計 $ 3 $ 個あり、これは $ A_1\ =\ 0 $ 個以上である - 友人 $ 2 $：ピース $ 2,\ 3,\ 4 $ にはいちごが合計 $ 6 $ 個あり、これは $ A_2\ =\ 6 $ 個以上である - 友人 $ 3 $：ピース $ 3,\ 4,\ 5 $ にはいちごが合計 $ 4 $ 個あり、これは $ A_3\ =\ 0 $ 個以上である - 友人 $ 4 $：ピース $ 4,\ 5,\ 0 $ にはいちごが合計 $ 9 $ 個あり、これは $ A_4\ =\ 9 $ 個以上である - 友人 $ 5 $：ピース $ 5,\ 0,\ 1 $ にはいちごが合計 $ 6 $ 個あり、これは $ A_5\ =\ 0 $ 個以上である したがって、チョコレートケーキ全体で $ 12 $ 個のいちごを置くことで、友人全員の希望を叶えることができます。 これが最小値となります。 ### Sample Explanation 3 ピース $ 0,\ 1,\ \dots,\ 9 $ の上に置くいちごの個数を、それぞれ $ 0,\ 0,\ 0,\ 4,\ 0,\ 1,\ 1,\ 1,\ 0,\ 5 $ とすると、友人全員の希望を叶えることができます。 このとき、チョコレートケーキ全体で $ 12 $ 個のいちごを置くことになり、これが最小値となります。 ### Sample Explanation 4 ピース $ 0 $ の上に $ 267503 $ 個、ピース $ 1 $ の上に $ 601617 $ 個のいちごを置くと、友人全員の希望を叶えることができます。