D - 流れ星の観測 解説 /

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

配点 : 400 点

問題文

高橋君は天文台で流れ星の観測を行っています。夜空を H 行 W 列のグリッドとしてモデル化しており、上から i 行目、左から j 列目の区画を (i, j) と表します（1 \leq i \leq H、1 \leq j \leq W）。行番号は上から下へ、列番号は左から右へ増加します。

この夜空には N 個の流れ星が出現します。k 番目の流れ星（1 \leq k \leq N）は、時刻 0 に区画 (R_k, C_k) に出現し、時刻が 1 進むごとに左上方向に 1 区画移動します。すなわち、時刻 t（t = 0, 1, 2, \ldots）において、k 番目の流れ星は区画 (R_k - t, C_k - t) に位置します。ただし、グリッドの外に出た流れ星（R_k - t < 1 または C_k - t < 1 となった場合）はその時刻以降存在しなくなります。

まとめると、k 番目の流れ星が存在する区画の集合は

\{(R_k - t,\ C_k - t) \mid t = 0, 1, \ldots, \min(R_k, C_k) - 1\}

です。

高橋君は、グリッド上の区画を 0 個以上選び、選んだ各区画にカメラを 1 台ずつ設置します。カメラを設置する区画はグリッド内の任意の区画から自由に選べます。各カメラはすべての時刻を通じて、設置された区画に固定されています。

ある流れ星がいずれかの時刻においてカメラの設置された区画に存在するならば、その流れ星はそのカメラによって撮影されます。1 台のカメラは、設置された区画を通過するすべての流れ星（異なる時刻に通過するものも含む）を撮影できます。

すべての流れ星がそれぞれ少なくとも 1 台のカメラによって撮影されるようにしたいとき、設置するカメラの台数の最小値を求めてください。

制約

  • 1 \leq H \leq 10^9
  • 1 \leq W \leq 10^9
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq R_k \leq H（1 \leq k \leq N）
  • 1 \leq C_k \leq W（1 \leq k \leq N）
  • (R_k, C_k) はすべて異なる（すなわち、どの 2 つの流れ星も初期位置が異なる）
  • 入力はすべて整数である

入力

H W N
R_1 C_1
R_2 C_2
\vdots
R_N C_N
  • 1 行目には、グリッドの行数 H、列数 W、流れ星の個数 N がスペース区切りで与えられる。
  • 続く N 行のうち k 行目（1 \leq k \leq N）には、k 番目の流れ星の初期位置の行番号 R_k と列番号 C_k がスペース区切りで与えられる。

出力

すべての流れ星を撮影するために必要なカメラの最小台数を 1 行で出力せよ。

入力例 1

5 5 5
3 3
4 4
5 5
2 4
4 2

出力例 1

3

入力例 2

3 4 4
1 4
2 2
3 1
3 4

出力例 2

4

入力例 3

20 20 18
1 1
2 2
3 3
4 4
5 5
6 1
7 2
8 3
9 4
10 5
1 10
2 11
3 12
15 1
16 2
20 10
10 20
11 19

出力例 3

7

入力例 4

1000000000 1000000000 40
1 1
1 1000000000
1000000000 1
1000000000 1000000000
999999999 999999999
999999998 999999997
999999997 999999998
500000000 500000000
500000001 500000000
500000000 500000001
123456789 987654321
987654321 123456789
314159265 271828182
271828182 314159265
42 999999999
999999999 42
2 2
3 3
4 4
5 5
10 20
20 10
100 200
200 100
1000 2000
2000 1000
12345 54321
54321 12345
111111111 222222222
222222222 111111111
333333333 444444444
444444444 333333333
555555555 666666666
666666666 555555555
777777777 888888888
888888888 777777777
135791357 246802468
246802468 135791357
999999000 999998000
999998000 999999000

出力例 4

23

入力例 5

1 1 1
1 1

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi is observing shooting stars at an observatory. He models the night sky as a grid with H rows and W columns, where the cell in the i-th row from the top and the j-th column from the left is denoted as (i, j) (1 \leq i \leq H, 1 \leq j \leq W). Row numbers increase from top to bottom, and column numbers increase from left to right.

N shooting stars appear in this night sky. The k-th shooting star (1 \leq k \leq N) appears at cell (R_k, C_k) at time 0, and moves one cell in the upper-left direction each time unit. That is, at time t (t = 0, 1, 2, \ldots), the k-th shooting star is located at cell (R_k - t, C_k - t). However, a shooting star that goes outside the grid (when R_k - t < 1 or C_k - t < 1) ceases to exist from that time onward.

In summary, the set of cells where the k-th shooting star exists is

\{(R_k - t,\ C_k - t) \mid t = 0, 1, \ldots, \min(R_k, C_k) - 1\}

Takahashi selects 0 or more cells on the grid and places one camera at each selected cell. The cells where cameras are placed can be freely chosen from any cells within the grid. Each camera remains fixed at its installed cell throughout all times.

If a shooting star is present at a cell where a camera is installed at any point in time, that shooting star is captured by that camera. A single camera can capture all shooting stars that pass through its installed cell (including those that pass through at different times).

Find the minimum number of cameras that need to be installed so that every shooting star is captured by at least one camera.

Constraints

  • 1 \leq H \leq 10^9
  • 1 \leq W \leq 10^9
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq R_k \leq H (1 \leq k \leq N)
  • 1 \leq C_k \leq W (1 \leq k \leq N)
  • All (R_k, C_k) are distinct (i.e., no two shooting stars share the same initial position)
  • All input values are integers

Input

H W N
R_1 C_1
R_2 C_2
\vdots
R_N C_N
  • The first line contains the number of rows H, the number of columns W, and the number of shooting stars N, separated by spaces.
  • The k-th of the following N lines (1 \leq k \leq N) contains the row number R_k and column number C_k of the initial position of the k-th shooting star, separated by spaces.

Output

Output in one line the minimum number of cameras required to capture all shooting stars.

Sample Input 1

5 5 5
3 3
4 4
5 5
2 4
4 2

Sample Output 1

3

Sample Input 2

3 4 4
1 4
2 2
3 1
3 4

Sample Output 2

4

Sample Input 3

20 20 18
1 1
2 2
3 3
4 4
5 5
6 1
7 2
8 3
9 4
10 5
1 10
2 11
3 12
15 1
16 2
20 10
10 20
11 19

Sample Output 3

7

Sample Input 4

1000000000 1000000000 40
1 1
1 1000000000
1000000000 1
1000000000 1000000000
999999999 999999999
999999998 999999997
999999997 999999998
500000000 500000000
500000001 500000000
500000000 500000001
123456789 987654321
987654321 123456789
314159265 271828182
271828182 314159265
42 999999999
999999999 42
2 2
3 3
4 4
5 5
10 20
20 10
100 200
200 100
1000 2000
2000 1000
12345 54321
54321 12345
111111111 222222222
222222222 111111111
333333333 444444444
444444444 333333333
555555555 666666666
666666666 555555555
777777777 888888888
888888888 777777777
135791357 246802468
246802468 135791357
999999000 999998000
999998000 999999000

Sample Output 4

23

Sample Input 5

1 1 1
1 1

Sample Output 5

1