分数: 800 点
问题陈述
数轴上有机器人。 具体来说,对于每个 i=0,1,2,\cdots,10^{100},只有一个机器人叫Robot i 位于坐标处 i.
我们有很多球。 每个球上都写有一个正整数。 整数序列 A 和 B,每个长度 N,描述这些球。 具体来说,对于每个 i (1 \leq i \leq N),有 B_i 球与 上面写着 A_i 。
现在,Snuke 将执行以下操作序列:
-
步骤 1:选择零个或多个球,并将这些球上写的整数替换为 正整数 他的选择 1 和 10^{100} (含)。 (新的整数可以彼此独立地选择。)
-
第二步:按照自己选择的任意顺序将球一粒一粒地吃掉。每次他吃球时,他应该做以下事情:
- 让 v 是他刚刚吃掉的球上写的整数。如果机器人 v 存在,移动它,使其坐标减少 1。在这里,如果目的地有另一个机器人,则该机器人(不是机器人 v)将被销毁。
Snuke 想要吃掉所有的球而不摧毁机器人 0。 找出 Snuke 在第 1 步中必须选择的最小球数才能实现其目标。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_1 < A_2 < \ldots < A_N \leq 10^9
- 1 \leq B_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
输出
打印答案。
示例输入 1
3 1 2 3 1 2 1
示例输出 1
1
我们可以通过选择一个球来实现目标 2 ,重写 3 就可以了,然后按以下顺序吃球:
-
吃球 上面写着 2 ,移动机器人 2 来自坐标 2 协调 1 并摧毁机器人 上面写着 1.
-
吃球 上面写着 3 ,移动机器人 3 来自坐标 3 协调 2.
-
吃球 上面写着 3 ,移动机器人 3 来自坐标 2 协调 1 并摧毁机器人 上面写着 2.
-
吃球 上面写着 1 。机器人 1 已经被摧毁,所以什么也没有发生。
示例输入 2
4 1 3 5 7 3 1 4 1
示例输出 2
0