分数: 100 点
问题陈述
勇敢的英雄Bitaro开始了打败怪物的冒险。
Bitaro有一个强度值,表示为 x,从初始值开始。 N 怪物,每个都标有数字 1 to N。为了打败 i- 第一个怪物 (1 \leq i \leq N),Bitaro 的实力至少为 A_i。击败 i第一个怪物使 Bitaro 的力量增加 B_i.
Bitaro想要使用以下策略击败所有怪物:
- 从特定的怪物开始 j (1 \leq j \leq N)并按顺序击败怪物: j, j + 1, \ldots, N.
- If j \geq 2,回去打败怪物 按顺序 1, 2, \ldots, j-1 。
给定怪物的信息,编写一个程序来确定最小初始强度 需要 x Bitaro才能击败所有怪物。
输入
从标准输入读取以下数据。
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
输出
输出单个整数,最小初始强度 x Bitaro才能击败所有怪物。
约束
- 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).
- 给定值均为整数。
子任务
- (10 点) N \leq 2\,000,以及最小初始强度 x is 10 或更少。
- (21 点) N \leq 2\,000.
- (19 分) 最小初始强度 x is 10 或更少。
- (22 点) B_i = 1 (1 \leq i \leq N).
- (28 点)没有额外的限制。
示例输入 1
5 1 3 2 8 6 4 3 1 1 2
示例输出 1
1
- 从初始强度开始 1.
- 按以下顺序击败怪物:
- 击败怪物 1。力量增加 4 to 5.
- 击败怪物 2。力量增加 3 to 8.
- 击败怪物 3。力量增加 1 to 9.
- 击败怪物 4。力量增加 1 to 10.
- 击败怪物 5。力量增加 2 to 12.
此示例输入满足子任务的约束 1,2,3 和 5.
示例输入 2
5 1 6 3 3 2 1 2 1 0 1
示例输出 2
3
- 从初始强度开始 3.
- 按以下顺序击败怪物:
- 击败怪物 3。力量增加 1 to 4.
- 击败怪物 4。力量增加 0 to 4.
- 击败怪物 5。力量增加 1 to 5.
- 击败怪物 1。力量增加 1 to 6.
- 击败怪物 2。力量增加 2 to 8.
此示例输入满足子任务的约束 1,2,3 和 5.
示例输入 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
此示例输入满足子任务的约束 1,2,3 和 5.