P11663 [JOI 2025 Final] 勇者比太郎 2 / Bitaro the Brave 2

译自 [第24回日本情報オリンピック 本選](https://contests.ioi-jp.org/joi-ho-2025/index.html) 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$ 解释 令 $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）无额外限制。