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 翻译