E - 基地局の設置 解説 /

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

配点 : 433 点

問題文

一直線の道路沿いに N 人の住民が住んでおり、1 から N までの番号が付けられています。道路を数直線とみなしたとき、住民 i は座標 X_i に住んでいます。なお、複数の住民が同じ座標に住んでいることもあります。

高橋君は、この道路上の好きな実数座標を選んで、ちょうど K 個の基地局を設置することにしました（同じ座標に複数の基地局を設置しても構いません）。

住民 i は、設置された基地局のうち少なくとも 1 つとの距離が R_i 以下であれば電波を受信できます。すなわち、ある基地局の座標 P について |X_i - P| \le R_i が成り立つとき、住民 i は電波を受信できます。

高橋君が適切に K 個の基地局を設置したとき、電波を受信できる住民の数の最大値を求めてください。

制約

  • 1 \leq N \leq 250
  • 1 \leq K \leq N
  • -10^9 \leq X_i \leq 10^9
  • 1 \leq R_i \leq 10^9
  • 入力はすべて整数

入力

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

N K
X_1 R_1
X_2 R_2
\vdots
X_N R_N
  • 1 行目には、住民の数を表す N と、設置する基地局の個数を表す K が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目（全体で 1+i 行目）には、住民 i の座標を表す X_i と、電波を受信できる最大距離を表す R_i が、スペース区切りで与えられる。

出力

電波を受信できる住民の数の最大値を 1 行に出力せよ。

入力例 1

4 2
1 2
3 1
8 2
10 3

出力例 1

4

入力例 2

5 1
-5 3
-5 2
0 1
7 2
10 1

出力例 2

2

入力例 3

15 3
-50 15
-40 10
-35 5
-20 8
-10 12
-5 5
0 10
5 3
12 6
20 15
45 20
50 10
60 5
80 25
100 10

出力例 3

11

入力例 4

40 6
-850000000 50000000
-820000000 60000000
-790000000 40000000
-750000000 70000000
-700000000 30000000
-550000000 80000000
-500000000 40000000
-480000000 50000000
-420000000 30000000
-400000000 60000000
-250000000 40000000
-220000000 50000000
-200000000 30000000
-180000000 70000000
-150000000 40000000
-100000000 50000000
-80000000 60000000
-50000000 20000000
-20000000 40000000
0 50000000
30000000 30000000
50000000 40000000
80000000 20000000
120000000 60000000
150000000 50000000
200000000 70000000
230000000 40000000
260000000 50000000
300000000 30000000
350000000 60000000
420000000 40000000
450000000 50000000
480000000 30000000
520000000 80000000
600000000 50000000
630000000 40000000
670000000 60000000
720000000 30000000
780000000 50000000
850000000 70000000

出力例 4

25

入力例 5

1 1
-1000000000 1000000000

出力例 5

1

Score : 433 pts

Problem Statement

There are N residents living along a straight road, numbered from 1 to N. Considering the road as a number line, resident i lives at coordinate X_i. Multiple residents may live at the same coordinate.

Takahashi has decided to choose any real coordinates on this road to install exactly K base stations (multiple base stations may be installed at the same coordinate).

Resident i can receive radio waves if the distance between them and at least one installed base station is at most R_i. That is, resident i can receive radio waves if |X_i - P| \le R_i holds for the coordinate P of some base station.

Find the maximum number of residents who can receive radio waves when Takahashi installs the K base stations optimally.

Constraints

  • 1 \leq N \leq 250
  • 1 \leq K \leq N
  • -10^9 \leq X_i \leq 10^9
  • 1 \leq R_i \leq 10^9
  • All input values are integers.

Input

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

N K
X_1 R_1
X_2 R_2
\vdots
X_N R_N
  • The first line contains N, representing the number of residents, and K, representing the number of base stations to install, separated by a space.
  • In the following N lines, the i-th line (the (1+i)-th line overall) contains X_i, representing the coordinate of resident i, and R_i, representing the maximum distance at which radio waves can be received, separated by a space.

Output

Print the maximum number of residents who can receive radio waves in one line.

Sample Input 1

4 2
1 2
3 1
8 2
10 3

Sample Output 1

4

Sample Input 2

5 1
-5 3
-5 2
0 1
7 2
10 1

Sample Output 2

2

Sample Input 3

15 3
-50 15
-40 10
-35 5
-20 8
-10 12
-5 5
0 10
5 3
12 6
20 15
45 20
50 10
60 5
80 25
100 10

Sample Output 3

11

Sample Input 4

40 6
-850000000 50000000
-820000000 60000000
-790000000 40000000
-750000000 70000000
-700000000 30000000
-550000000 80000000
-500000000 40000000
-480000000 50000000
-420000000 30000000
-400000000 60000000
-250000000 40000000
-220000000 50000000
-200000000 30000000
-180000000 70000000
-150000000 40000000
-100000000 50000000
-80000000 60000000
-50000000 20000000
-20000000 40000000
0 50000000
30000000 30000000
50000000 40000000
80000000 20000000
120000000 60000000
150000000 50000000
200000000 70000000
230000000 40000000
260000000 50000000
300000000 30000000
350000000 60000000
420000000 40000000
450000000 50000000
480000000 30000000
520000000 80000000
600000000 50000000
630000000 40000000
670000000 60000000
720000000 30000000
780000000 50000000
850000000 70000000

Sample Output 4

25

Sample Input 5

1 1
-1000000000 1000000000

Sample Output 5

1