第 2 题 勇者比太郎 2 (bitarothebrave2)

时间限制 1.0 s · 空间限制 256 MB · 79 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 bitarothebrave2.in，输出文件 bitarothebrave2.out。

译自 第24回日本情報オリンピック 本選 T2。

题目描述

比太郎要打怪。

令比太郎初始时的力量为 $x$。有 $N$ 个怪物，编号 $1 \sim N$。欲打败第 $i$（$1 \le i \le N$）个怪物，需要力量 $\ge A_i$。打败第 $i$（$1 \le i \le N$）个怪物，会使比太郎的力量增加 $B_i$。

比太郎会用如下的策略打怪：

• 选择整数 $j$（$1 \le j \le N$），然后按 $j, j+1, \cdots, N$ 的顺序打怪。
• 如果 $j \ge 2$，回头按顺序打怪物 $1, 2, \cdots, j-1$。

在按照策略打完所有的怪物的前提下，求出比太郎初始力量 $x$ 的最小值。

输入格式

如下所示：

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

$B_1$ $B_2$ $\cdots$ $B_N$

输出格式

输出一行一个整数，即比太郎初始力量 $x$ 的最小值。

样例

样例 1

输入：

5
1 3 2 8 6
4 3 1 1 2

输出：

1

样例 2

输入：

5
1 6 3 3 2
1 2 1 0 1

输出：

3

样例 3

输入：

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

输出：

9

样例 4

输入：

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

输出：

0

提示

样例解释

样例 1 解释

令 $x = 1$，然后按照 $1 \to 5$ 的顺序打怪。

该样例满足子任务 1, 2, 3, 5 的限制。

样例 2 解释

令 $x = 3$，然后先打 $3 \to 5$ 的怪，再打 $1 \to 2$ 的怪。

该样例满足子任务 1, 2, 3, 5 的限制。

样例 3 解释

该样例满足所有子任务的限制。

样例 4 解释

该样例满足子任务 1, 2, 3, 5 的限制。

数据范围

• $2 \le N \le 5 \times 10^5$。
• $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. （10pts）$N \le 2,000$，保证答案不大于 10。
2. （21pts）$N \le 2,000$。
3. （19pts）保证答案不大于 10。
4. （22pts）$B_i = 1$（$1 \le i \le N$）；
5. （28pts）无额外限制。