You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

题目译自 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)$。
• 输入的所有值均为整数。

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