题目描述

题目译自 JOI 2025 Final T2 「勇者ビ太郎 2 / Bitaro the Brave 2」

勇者比太郎决定出发冒险，讨伐所有的怪物。比太郎有一个代表力量的值，初始为 $x$。共有 $N$ 个怪物，从 $1$ 到 $N$ 编号。要击败怪物 $i$ $(1 \leq i \leq N)$，比太郎的力量必须至少为 $A_i$。击败怪物 $i$ 后，比太郎的力量会增加 $B_i$。

比太郎希望通过以下方式击败所有怪物：

• 从某个 $j$ $(1 \leq j \leq N)$ 开始，依次击败怪物 $j, j+1, \ldots, N$。
• 如果 $j \geq 2$，再依次击败怪物 $1, 2, \ldots, j-1$。

给定所有怪物的信息，编写一个程序计算比太郎击败所有怪物所需的最小初始力量值 $x$。

输入格式

第一行包含一个整数 $N$。

第二行包含用空格分隔的 $N$ 个整数 $A_1, A_2, \ldots A_N$。

第三行包含用空格分隔的 $N$ 个整数 $B_1, B_2, \ldots B_N$。

输出格式

输出比太郎击败所有怪物所需的最小初始力量值 $x$。

5
1 3 2 8 6
4 3 1 1 2

1

在初始力量为 $1$ 时，可以按以下顺序击败所有怪物：

• 初始力量为 $1$。
• 击败怪物 $1$，力量增加 $4$，变为 $5$。
• 击败怪物 $2$，力量增加 $3$，变为 $8$。
• 击败怪物 $3$，力量增加 $1$，变为 $9$。
• 击败怪物 $4$，力量增加 $1$，变为 $10$。
• 击败怪物 $5$，力量增加 $2$，变为 $12$。

没有初始力量为 $0$ 或更低的方法击败所有怪物，因此输出 $1$。

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

5
1 6 3 3 2
1 2 1 0 1

3

在初始力量为 $3$ 时，可以按以下顺序击败所有怪物：

• 初始力量为 $3$。
• 击败怪物 $3$，力量增加 $1$，变为 $4$。
• 击败怪物 $4$，力量增加 $0$，变为 $4$。
• 击败怪物 $5$，力量增加 $1$，变为 $5$。
• 击败怪物 $1$，力量增加 $1$，变为 $6$。
• 击败怪物 $2$，力量增加 $2$，变为 $8$。

没有初始力量为 $2$ 或更低的方法击败所有怪物，因此输出 $3$。

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

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,2,3,5$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 500000$。
• $0 \leq A_i \leq 10^9$ $(1 \leq i \leq N)$。
• $0 \leq B_i \leq 10^9$ $(1 \leq i \leq N)$。
• 输入的所有值均为整数。

详细子任务附加限制及分值如下表所示。