C - Robots Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

数直線上にロボットがいます． 具体的には，各 i=0,1,2,\cdots,10^{100} について，座標 i に 1 台のロボットがおり，ロボット i と呼ばれています．

たくさんのボールがあります． それぞれのボールには，正整数が 1 つ書いてあります． これらのボールの情報は，長さ N の整数列 A と B で表されます． 具体的には，各 i (1 \leq i \leq N) について，A_i の書かれたボールが B_i 個あります．

今からすぬけくんは，次の操作を行います．

  • Step 1: 0 個以上のボールを選び，そこに書かれている整数を，1 以上 10^{100} 以下の好きな正整数に書き換える．（ボールごとに書き換える整数を選択できる）

  • Step 2: ボールを 1 つずつ食べる．ボールを食べる順番は自由に選べる．ボールを食べるたびに，以下の操作を行う．

    • 今食べたボールに書かれた整数を v とする．ロボット v が存在するなら，それを，現在の座標より 1 小さい座標へ移動させる．もし移動先に別のロボットがいるなら，そのロボットは破壊される．（ロボット v は無事である）

すぬけくんは，ロボット 0 が破壊されないように，すべてのボールを食べきりたいです． すぬけくんが目標を達成するために Step 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 の書かれたボールを 1 つ選び，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

Score : 800 points

Problem Statement

There are robots on a number line. Specifically, for each i=0,1,2,\cdots,10^{100}, there is exactly one robot called Robot i at coordinate i.

We have many balls. Each of the balls has a positive integer written on it. Integer sequences A and B, each of length N, describe these balls. Specifically, for each i (1 \leq i \leq N), there are B_i balls with A_i written on them.

Now, Snuke will do the following sequence of operations:

  • Step 1: Choose zero or more balls and replace the integers written on those balls with positive integers of his choice between 1 and 10^{100} (inclusive). (The new integers can be chosen independently from each other.)

  • Step 2: Eat the balls one by one in any order of his choice. Each time he eats a ball, he should do the following:

    • Let v be the integer written on the ball he has just eaten. If Robot v exists, move it so that its coordinate decreases by 1. Here, if there is another robot at the destination, that robot (not Robot v) will be destroyed.

Snuke wants to eat all the balls without destroying Robot 0. Find the minimum number of balls Snuke must choose in Step 1 to achieve his objective.

Constraints

  • 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

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

Output

Print the answer.

Sample Input 1

3
1 2 3
1 2 1

Sample Output 1

1

We can achieve the objective by choosing one ball with 2 written on it, rewriting 3 on it, and then eating the balls in the following order:

  • Eat the ball with 2 written on it, moving Robot 2 from coordinate 2 to coordinate 1 and destroying Robot 1.

  • Eat the ball with 3 written on it, moving Robot 3 from coordinate 3 to coordinate 2.

  • Eat the ball with 3 written on it, moving Robot 3 from coordinate 2 to coordinate 1 and destroying Robot 2.

  • Eat the ball with 1 written on it. Robot 1 is already destroyed, so nothing happens.

Sample Input 2

4
1 3 5 7
3 1 4 1

Sample Output 2

0