F - IRU vs SAKI Editorial /

Time Limit: 2 sec / Memory Limit: 128 MB

Description

2次元平面上にマラカス(点)がn個ある． バスターでマラカスをなるべくたくさん撃ち抜きたい． バスターは幅2w，長さ無限大の矩形の大きさを持ち，矩形の幅の中心を原点が通るように原点から発射される． 適切にバスターを打ち出す角度を決めたとき最大何個のマラカスを撃ち抜けるか答えよ．

Input

入力は複数のテストケースからなる．入力の終わりは2つの0のみを含んだ行で示される． 各テストケースは以下の形式で与えられる． 

n w
x_1 y_1
…
x_n y_n
  • 1≦n≦100,000
  • 1≦w≦1,000
  • 0≦x_i，y_i≦100,000

テストケースの1行目には2つの整数n，wが書かれている． nはマラカスの数を表し，wはバスターの半径を表す．

続くn行にはそれぞれ2つの整数x_i，y_iが書かれている． x_i，y_iはi番目のマラカスの座標を表す．

2つのテストケースの間には空行がひとつ入る．

wを±10^{-6}変更しても答えは変わらないことが保証されている． テストケースの数は1つのファイルにつき1,000個以下であることが保証されている． また，1つのファイルにつきnの合計は300,000以下であることが保証されている．

Output

各テストケースに対して，撃ち抜けるマラカスの最大個数を1行に出力せよ．

Sample Input

1 1
2 2

4 1
3 3
4 4
5 5
6 6

3 2
1 1
2 1
3 1

7 3
10 3
10 5
10 7
10 9
10 11
10 13
10 15

2 1000
10 10
10 10

5 10
100 20
110 21
48 9
4 240
5 2012

0 0

Sample Output

1
4
3
5
2
3

Hint

サンプルの4つ目のテストケースは以下の様にすれば5個のマラカスを撃ち抜ける． 画像はイメージです．実際と異なる場合がございます．

Source Name

ふか杯 5th Contest