题目描述

AtCoder さんは $2N$ 人の友人のために、円形のチョコレートケーキを作りました。このケーキは中心から放射状に $2N$ 個のピースに等分されており、各ピースには時計回りの順番で $0$ から $2N-1$ までの番号が付けられています。

いま、最後の仕上げとして、AtCoder さんはこのケーキの各ピースの上にいちごを乗せようとしており、そのために友人に希望を聞きました。友人には $0$ から $2N-1$ までの番号が付けられており、友人 $i\ (0\ \leq\ i\ \leq\ 2N-1)$ の希望は以下の通りです。

• ピース $i,\ i+1,\ \dots,\ i+N-1$ には、合計で $A_i$ 個以上のいちごが乗せられていてほしい（ただし、$x\ \geq\ 2N$ に対しては、ピース $x$ はピース $x-2N$ のことを指すものとする）

友人全員の希望を叶えるためには、ケーキ全体に最小で何個のいちごを乗せる必要があるでしょうか？

输入格式

入力は以下の形式で標準入力から与えられます。

$N$ $A_0$ $A_1$ $\cdots$ $A_{2N-1}$

输出格式

友人全員の希望を叶えるために乗せる必要のあるいちごの個数の最小値を出力してください。

题目大意

题目描述

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}$。

其含义已在题意中解释。

输出格式

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

3
2 5 7 4 2 1

8

3
8 0 6 0 9 0

12

5
3 1 5 7 0 8 4 6 4 9

12

1
267503 601617

869120

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

513119404

提示

制約

• $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$ 個のいちごを置くと、友人全員の希望を叶えることができます。