题目背景

译自 第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$ 的最小值。

5
1 3 2 8 6
4 3 1 1 2

1

5
1 6 3 3 2
1 2 1 0 1

3

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

9

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）无额外限制。