AT_joi2025ho_b.勇者ビ太郎 2 (Bitaro the Brave 2)

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

Bitaro 有一个力量值，用 $x$ 表示，初始时为某个值。有 $N$ 个怪物，每个怪物编号从 $1$ 到 $N$。击败第 $i$ 只怪物（$1 \leq i \leq N$），Bitaro 的力量至少要达到 $A_i$。击败第 $i$ 只怪物后，Bitaro 的力量会增加 $B_i$。

Bitaro 想用如下策略击败所有怪物：

1. 选择某个怪物 $j$（$1 \leq j \leq N$），先依次击败 $j, j+1, \ldots, N$ 号怪物。
2. 如果 $j \geq 2$，再依次击败 $1, 2, \ldots, j-1$ 号怪物。

给出所有怪物的信息，请编写一个程序，求出能击败所有怪物所需的最小初始力量值 $x$。

---

从标准输入读取数据。

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

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

---

子任务

1.（$10$ 分）$N \leq 2\,000$，且最小初始力量 $x \leq 10$。
2.（$21$ 分）$N \leq 2\,000$。
3.（$19$ 分）最小初始力量 $x \leq 10$。
4.（$22$ 分）$B_i=1$（$1 \leq i \leq N$）。
5.（$28$ 分）无额外约束。

---

样例解释 1

• 初始力量为 $1$。
• 击败怪物的顺序如下：
  1. 打败第 $1$ 号怪物，力量增加 $4$，达到 $5$。
  2. 打败第 $2$ 号怪物，力量增加 $3$，达到 $8$。
  3. 打败第 $3$ 号怪物，力量增加 $1$，达到 $9$。
  4. 打败第 $4$ 号怪物，力量增加 $1$，达到 $10$。
  5. 打败第 $5$ 号怪物，力量增加 $2$，达到 $12$。

该输入满足子任务 $1,2,3,5$ 的约束。

---

样例解释 2

• 初始力量为 $3$。
• 按如下顺序击败怪物：
  1. 击败第 $3$ 号怪物，力量增加 $1$，达到 $4$。
  2. 击败第 $4$ 号怪物，力量增加 $0$，达到 $4$。
  3. 击败第 $5$ 号怪物，力量增加 $1$，达到 $5$。
  4. 击败第 $1$ 号怪物，力量增加 $1$，达到 $6$。
  5. 击败第 $2$ 号怪物，力量增加 $2$，达到 $8$。

该输入满足子任务 $1,2,3,5$ 的约束。

---

样例解释 3

该输入满足所有子任务的约束。

---

样例解释 4

该输入满足子任务 $1,2,3,5$ 的约束。

数据范围

• $2 \leq N \leq 500\,000$
• $0 \leq A_i \leq 10^9$（$1 \leq i \leq N$）
• $0 \leq B_i \leq 10^9$（$1 \leq i \leq N$）
• 输入的所有值均为整数。

由 ChatGPT 5 翻译