G - Catch All Apples 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 625 点

問題文

数直線上に N 個のリンゴが落ちてきます。リンゴ i は時刻 T_i に座標 X_i に落ちてきます。

あなたは数直線上にいくつかのリンゴロボを置いて N 個のリンゴを全て回収したいです。リンゴロボは好きな座標に配置することができます。

リンゴロボは時刻 0 から作動し、数直線上を左右に速さ 1 以下で自由に動かすことができます。複数のリンゴロボが同じ時刻に同じ座標にいることもできます。各リンゴロボは時刻 T_i に座標 X_i にいる時、またその時に限りリンゴ i を回収することができます。

全てのリンゴを回収するために必要なリンゴロボの台数の最小値を求めてください。

制約

  • 1\le N\le 3\times 10^5
  • 0\le T_i\le 3\times 10^5
  • 0\le X_i\le 3\times 10^5
  • (T_i,X_i) \neq (T_j,X_j) (i\neq j)
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
T_1 X_1
T_2 X_2
\vdots
T_N X_N

出力

答えを出力せよ。

入力例 1

4
0 2
1 0
2 1
2 3

出力例 1

2

以下のようにリンゴロボを動かすことで 2 台のリンゴロボで全てのリンゴを回収することができます：

  • リンゴロボ 1 を座標 0 に、リンゴロボ 2 を座標 2 に配置する。
  • 時刻 0：リンゴロボ 2 がリンゴ 1 を回収する。
  • 時刻 1：リンゴロボ 1 がリンゴ 2 を回収する。時刻 2 まで両方のリンゴロボを速さ 1 で正方向に動かす。
  • 時刻 2：リンゴロボ 1 がリンゴ 3 を、リンゴロボ 2 がリンゴ 4 を回収する。

2 台未満のリンゴロボで全てのリンゴを回収することはできないので、2 を出力してください。

入力例 2

5
0 1
0 2
0 3
0 4
0 5

出力例 2

5

入力例 3

8
10 4
4 2
7 10
5 3
1 9
0 6
3 8
0 9

出力例 3

2

Score : 625 points

Problem Statement

N apples fall on a number line. Apple i falls at coordinate X_i at time T_i.

You want to place some robots on the number line to collect all N apples. The robots can be placed at any coordinates.

Each robot starts operating from time 0 and can move freely along the number line at a speed of at most 1. Multiple robots may occupy the same coordinate at the same time. Each robot can collect apple i if and only if it is at coordinate X_i at time T_i.

Find the minimum number of robots needed to collect all apples.

Constraints

  • 1 \le N \le 3 \times 10^5
  • 0 \le T_i \le 3 \times 10^5
  • 0 \le X_i \le 3 \times 10^5
  • (T_i, X_i) \neq (T_j, X_j) (i \neq j)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
T_1 X_1
T_2 X_2
\vdots
T_N X_N

Output

Output the answer.

Sample Input 1

4
0 2
1 0
2 1
2 3

Sample Output 1

2

All apples can be collected with two robots by moving them as follows:

  • Place robot 1 at coordinate 0 and robot 2 at coordinate 2.
  • Time 0: Robot 2 collects apple 1.
  • Time 1: Robot 1 collects apple 2. Move both robots in the positive direction at speed 1 until time 2.
  • Time 2: Robot 1 collects apple 3 and robot 2 collects apple 4.

It is impossible to collect all apples with fewer than two robots, so output 2.

Sample Input 2

5
0 1
0 2
0 3
0 4
0 5

Sample Output 2

5

Sample Input 3

8
10 4
4 2
7 10
5 3
1 9
0 6
3 8
0 9

Sample Output 3

2