勇敢的英雄 Bitaro 踏上了击败怪物的冒险之旅。

Bitaro 拥有一个力量值，记为 $x$，初始时有一个初始值。共有 $N$ 只怪物，每只怪物都标有从 $1$ 到 $N$ 的编号。为了击败第 $i$ 只怪物（$1 \le i \le N$），Bitaro 的力量值必须至少为 $A_i$。击败第 $i$ 只怪物后，Bitaro 的力量值会增加 $B_i$。

Bitaro 想要使用以下策略击败所有怪物：

1. 从特定的怪物 $j$（$1 \le j \le N$）开始，按顺序击败怪物：$j, j + 1, \dots, N$。
2. 如果 $j \ge 2$，则返回并按顺序击败怪物 $1, 2, \dots, j - 1$。

给定关于怪物的信息，编写一个程序来确定 Bitaro 击败所有怪物所需的最小初始力量值 $x$。

输入格式

从标准输入读取以下数据：

$N$ $A_1 \ A_2 \ \dots \ A_N$ $B_1 \ B_2 \ \dots \ B_N$

输出格式

输出一个整数，表示 Bitaro 击败所有怪物所需的最小初始力量值 $x$。

数据范围

• $2 \le N \le 500\,000$。
• $0 \le A_i \le 10^9$（$1 \le i \le N$）。
• $0 \le B_i \le 10^9$（$1 \le i \le N$）。
• 给定值均为整数。

子任务

1. （10 分）$N \le 2\,000$，且最小初始力量值 $x$ 不超过 $10$。
2. （21 分）$N \le 2\,000$。
3. （19 分）最小初始力量值 $x$ 不超过 $10$。
4. （22 分）$B_i = 1$（$1 \le i \le N$）。
5. （28 分）无附加限制。

样例

样例输入 1

5
1 3 2 8 6
4 3 1 1 2

样例输出 1

1

说明

• 以初始力量值 $1$ 开始。
• 按以下顺序击败怪物：
  1. 击败怪物 1。力量值增加 4，变为 5。
  2. 击败怪物 2。力量值增加 3，变为 8。
  3. 击败怪物 3。力量值增加 1，变为 9。
  4. 击败怪物 4。力量值增加 1，变为 10。
  5. 击败怪物 5。力量值增加 2，变为 12。

样例输入 2

5
1 6 3 3 2
1 2 1 0 1

样例输出 2

3

说明

• 以初始力量值 $3$ 开始。
• 按以下顺序击败怪物：
  1. 击败怪物 3。力量值增加 1，变为 4。
  2. 击败怪物 4。力量值增加 0，变为 4。
  3. 击败怪物 5。力量值增加 1，变为 5。
  4. 击败怪物 1。力量值增加 1，变为 6。
  5. 击败怪物 2。力量值增加 2，变为 8。

样例输入 3

10
11 9 8 12 7 7 8 12 9 10
1 1 1 1 1 1 1 1 1 1

样例输出 3

9

样例输入 4

7
1125 638 0 37 737 820 1202
23 984 558 350 52 345 580

样例输出 4

0