시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 43 14 8 29.630%

문제

학생들은 프로그래밍 시간에 계속해서 떠들고 있다. 더 이상 참지 못한 조쌤은 자리를 박차고 애들을 잡기 위해 뛰기 시작했고 이와 동시에 떠들던 N명의 학생은 도망가기 시작했다.

현재 조쌤은 (BX, BY) 위치에 있다. 그리고 뛰기 시작한 조쌤은 t초 후 (BX+BVX*t, BY+BVY*t) 위치에 있게 된다. 즉 조쌤은 초당 (BVX, BVY) 방향으로 뛰고 있는 것이다.

N명의 학생 역시 현재 (Xi, Yi)에 위치하고 있고 t(t ≥ 0)초 후 (Xi+VXi*t, Yi+VYi*t) 위치에 있게 된다.

조쌤은 현재 자신 위치에서 반경이 R인 원 안에 있는 아이들은 모조리 잡을 수 있다. 하지만 위의 조건을 살펴보면 현재 아이들과 조쌤 모두 뛰는 상황이기에 시간마다 아이들을 잡을 수 있는 숫자가 변한다. 조쌤은 한 번 잡고나면 잡히지 않은 아이들은 모두 도망간 상태기 때문에 단 한번의 기회에 최대한 많은 아이들을 잡고 싶다.

문제는 조쌤과 학생들의 위치 및 뛰는 방향이 주어지면 한 번에 얼마나 많은 학생을 잡을 수 있는지 구하는 것이다. 물론, 최대한 많이 잡을 수 있는 시간이 정수가 아닌 소수일 수도 있다.

입력

첫 줄에는 학생의 수 N(1 ≤ N ≤ 50,000)과 조쌤이 잡을 수 있는 반경 R(1 ≤ R ≤ 2,500), 그리고 조쌤의 위치를 나타내는 BX, BY(-1,000 ≤ BX, BY ≤ 1,000)와 조쌤이 뛰는 방향을 나타내는 BVX, BVY(-100 ≤ BVX, BVY ≤ 100)가 공백으로 구분되어 주어진다. 두 번째 줄부터 N+1번째 줄까지는 각 학생의 정보가 주어지는데 각 줄에는 학생의 초기 위치 Xi, Yi와 뛰는 방향 VXi, VYi(-1,000 ≤ Xi, Yi, VXi, VYi ≤ 1,000)가 공백으로 구분되어 주어진다. 입력되는 모든 수는 정수이다.

출력

첫 줄에 조쌤이 한 번에 잡을 수 있는 최대 학생 숫자를 출력한다. 실수 오차 조정을 위해 학생과 조교 사이의 거리가 R±0.0001이라면 잡을 수 있다고 한다.

예제 입력 1

3 1 0 0 0 2
0 -3 0 4
1 2 -1 1
1 -2 2 -1

예제 출력 1

2

힌트

1.5초의 시간이 흐른 후 조쌤은 (0, 3)에 위치해 있고 각 학생은 (0, 3), (-0.5, 3.5), (4, -3.5)에 위치하여 있다. 즉 반경 1 안에 있는 1, 2번 학생을 조쌤은 잡을 수 있고 이것이 한 번에 잡을 수 있는 최대 학생 수가 된다.
W3sicHJvYmxlbV9pZCI6IjExNzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4NzBcdWMzMjRcdWQzZWNcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHVjMmRjXHVhYzA0XHVjNWQwIFx1YWNjNFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWI1YTBcdWI0ZTRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1Y2MzOFx1YzljMCBcdWJhYmJcdWQ1NWMgXHVjODcwXHVjMzI0XHVjNzQwIFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWJjMTVcdWNjMjhcdWFjZTAgXHVjNTYwXHViNGU0XHVjNzQ0IFx1YzdhMVx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViNmYwXHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU4OFx1YWNlMCBcdWM3NzRcdWM2NDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YjVhMFx1YjRlNFx1YjM1OCBOXHViYTg1XHVjNzU4IFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWIzYzRcdWI5ZGRcdWFjMDBcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTg4XHViMmU0LjxcL3A+XHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWM4NzBcdWMzMjRcdWM3NDAgKEJYLCBCWSkgXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjZmMFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NWMgXHVjODcwXHVjMzI0XHVjNzQwIHRcdWNkMDggXHVkNmM0IChCWCtCVlgqdCwgQlkrQlZZKnQpIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM5ODkgXHVjODcwXHVjMzI0XHVjNzQwIFx1Y2QwOFx1YjJmOSAoQlZYLCBCVlkpIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWI2ZjBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD5OXHViYTg1XHVjNzU4IFx1ZDU1OVx1YzBkZCBcdWM1ZWRcdWMyZGMgXHVkNjA0XHVjN2FjIChYaSwgWWkpXHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWFjZTAgdCh0ICZnZTsgMClcdWNkMDggXHVkNmM0IChYaStWWGkqdCwgWWkrVllpKnQpIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcbjxwPlx1Yzg3MFx1YzMyNFx1Yzc0MCBcdWQ2MDRcdWM3YWMgXHVjNzkwXHVjMmUwIFx1YzcwNFx1Y2U1OFx1YzVkMFx1YzExYyBcdWJjMThcdWFjYmRcdWM3NzQgUlx1Yzc3OCBcdWM2ZDAgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM1NDRcdWM3NzRcdWI0ZTRcdWM3NDAgXHViYWE4XHVjODcwXHViOWFjIFx1YzdhMVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjNzA0XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWMwYjRcdWQzYjRcdWJjZjRcdWJhNzQgXHVkNjA0XHVjN2FjIFx1YzU0NFx1Yzc3NFx1YjRlNFx1YWNmYyBcdWM4NzBcdWMzMjQgXHViYWE4XHViNDUwIFx1YjZmMFx1YjI5NCBcdWMwYzFcdWQ2NjlcdWM3NzRcdWFlMzBcdWM1ZDAgXHVjMmRjXHVhYzA0XHViOWM4XHViMmU0IFx1YzU0NFx1Yzc3NFx1YjRlNFx1Yzc0NCBcdWM3YTFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViY2MwXHVkNTVjXHViMmU0LiBcdWM4NzBcdWMzMjRcdWM3NDAgXHVkNTVjIFx1YmM4OCBcdWM3YTFcdWFjZTBcdWIwOThcdWJhNzQgXHVjN2ExXHVkNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWM1NDRcdWM3NzRcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIFx1YjNjNFx1YjlkZFx1YWMwNCBcdWMwYzFcdWQwZGNcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjJlOCBcdWQ1NWNcdWJjODhcdWM3NTggXHVhZTMwXHVkNjhjXHVjNWQwIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHVjNTQ0XHVjNzc0XHViNGU0XHVjNzQ0IFx1YzdhMVx1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuPHA+XHViYjM4XHVjODFjXHViMjk0IFx1Yzg3MFx1YzMyNFx1YWNmYyBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjNzA0XHVjZTU4IFx1YmMwZiBcdWI2ZjBcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCBcdWQ1NWMgXHViYzg4XHVjNWQwIFx1YzViY1x1YjljOFx1YjA5OCBcdWI5Y2VcdWM3NDAgXHVkNTU5XHVjMGRkXHVjNzQ0IFx1YzdhMVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YmIzY1x1Yjg2MCwgXHVjZDVjXHViMzAwXHVkNTVjIFx1YjljZVx1Yzc3NCBcdWM3YTFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjODE1XHVjMjE4XHVhYzAwIFx1YzU0NFx1YjJjYyBcdWMxOGNcdWMyMThcdWM3N2MgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyA1MCwwMDApXHVhY2ZjIFx1Yzg3MFx1YzMyNFx1Yzc3NCBcdWM3YTFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMThcdWFjYmQgUigxICZsZTsgUiAmbGU7IDIsNTAwKSwgXHVhZGY4XHViOWFjXHVhY2UwIFx1Yzg3MFx1YzMyNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IEJYLCBCWSgtMSwwMDAgJmxlOyBCWCwgQlkgJmxlOyAxLDAwMClcdWM2NDAgXHVjODcwXHVjMzI0XHVjNzc0IFx1YjZmMFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IEJWWCwgQlZZKC0xMDAgJmxlOyBCVlgsIEJWWSAmbGU7IDEwMClcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE4rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzBcdWIyOTQgXHVhYzAxIFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTU5XHVjMGRkXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWM3MDRcdWNlNTggWGksIFlpXHVjNjQwIFx1YjZmMFx1YjI5NCBcdWJjMjlcdWQ1YTUgVlhpLCBWWWkoLTEsMDAwICZsZTsgWGksIFlpLCBWWGksIFZZaSAmbGU7IDEsMDAwKVx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHViNDE4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyMThcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM4NzBcdWMzMjRcdWM3NzQgXHVkNTVjIFx1YmM4OFx1YzVkMCBcdWM3YTFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTU5XHVjMGRkIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzJlNFx1YzIxOCBcdWM2MjRcdWNjMjggXHVjODcwXHVjODE1XHVjNzQ0IFx1YzcwNFx1ZDU3NCBcdWQ1NTlcdWMwZGRcdWFjZmMgXHVjODcwXHVhZDUwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWFjMDAgUiZwbHVzbW47MC4wMDAxXHVjNzc0XHViNzdjXHViYTc0IFx1YzdhMVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiIxLjVcdWNkMDhcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1ZDc1MFx1Yjk3OCBcdWQ2YzQgXHVjODcwXHVjMzI0XHVjNzQwICgwLCAzKVx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NzQgXHVjNzg4XHVhY2UwIFx1YWMwMSBcdWQ1NTlcdWMwZGRcdWM3NDAgKDAsIDMpLCAoLTAuNSwgMy41KSwgKDQsIC0zLjUpXHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU1OFx1YzVlYyBcdWM3ODhcdWIyZTQuIFx1Yzk4OSBcdWJjMThcdWFjYmQgMSBcdWM1NDhcdWM1ZDAgXHVjNzg4XHViMjk0IDEsIDJcdWJjODggXHVkNTU5XHVjMGRkXHVjNzQ0IFx1Yzg3MFx1YzMyNFx1Yzc0MCBcdWM3YTFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YWNlMCBcdWM3NzRcdWFjODNcdWM3NzQgXHVkNTVjIFx1YmM4OFx1YzVkMCBcdWM3YTFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTU5XHVjMGRkIFx1YzIxOFx1YWMwMCBcdWI0MWNcdWIyZTQuXHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTE3NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNhdHRsZSBCcnVpc2VycyIsImRlc2NyaXB0aW9uIjoiPHA+Q2FubXV1IGlzIG91dCBmb3IgcmV2ZW5nZSBhZnRlciBiZWluZyB1dHRlcmx5IGRlZmVhdGVkIGJ5IEJlc3NpZSBpbiBwYWludGJhbGwgYW5kIGhhcyBjaGFsbGVuZ2VkIEJlc3NpZSB0byBhIHZpZGVvIGdhbWUuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgZ2FtZSwgQmVzc2llIHN0YXJ0cyBvdXQgYXQgcG9pbnQgKEJYLCBCWSkgaW4gdGhlIGNvb3JkaW5hdGUgZ3JpZCAoLTEsMDAwICZsdDs9IEJYICZsdDs9IDEsMDAwOyAtMTAwMCAmbHQ7PSBCWSAmbHQ7PSAxLDAwMCksIGFuZCB0cmllcyB0byBlc2NhcGUsIHN0YXJ0aW5nIGF0IHRpbWUgMC4gU2hlIG1vdmVzIGNvbnRpbnVvdXNseSBhdCBhIHZlbG9jaXR5IG9mIChCVlgsIEJWWSkgdW5pdHNcL3NlY29uZCAoLTEwMCAmbHQ7PSBCVlggJmx0Oz0gMTAwOyAtMTAwICZsdDs9IEJWWSAmbHQ7PSAxMDApLiBUaHVzLCBhdCB0aW1lIDEgc2hlIHdpbGwgYmUgYXQgcG9pbnQgKEJYICsgQlZYLCBCWSArIEJWWSk7IGF0IHRpbWUgMS41IHNoZSB3aWxsIGJlIGF0IChCWCArIDEuNSpCVlgsIEJZICsgMS41KkJWWSkuPFwvcD5cclxuXHJcbjxwPlVuZm9ydHVuYXRlbHksIENhbm11dSBoYXMgc2VudCBOICgxICZsdDs9IE4gJmx0Oz0gNTAsMDAwKSBjYXR0bGUgYnJ1aXNlcnMgdG8gcHVyc3VlIEJlc3NpZS4gJm5ic3A7QXQgdGltZSB0PTAsIGNhdHRsZSBicnVpc2VyIGkgaXMgYXQgcG9zaXRpb24gKFhfaSwgWV9pKSAoLTEsMDAwICZsdDs9IFhfaSAmbHQ7PSAxLDAwMDsgLTEsMDAwICZsdDs9IFlfaSAmbHQ7PSAxLDAwMCkgd2l0aCB2ZWxvY2l0eSAoVlhfaSwgVllfaSkgdW5pdHNcL3NlY29uZCAoLTEsMDAwICZsdDs9IFZYX2kgJmx0Oz0gMSwwMDA7IC0xLDAwMCAmbHQ7PSBWWV9pICZsdDs9IDEsMDAwKS48XC9wPlxyXG5cclxuPHA+RWFjaCBjYXR0bGUgYnJ1aXNlciBjYXJyaWVzIGEgJnF1b3Q7cHJveGltaXR5JnF1b3Q7IHdlYXBvbiB0byBmaXJlIGF0IEJlc3NpZTsgdGhlIHdlYXBvbiBjYW4gaHVydCBCZXNzaWUgd2hlbiB0aGUgY2F0dGxlIGJydWlzZXIgaXMgbm8gZnVydGhlciB0aGFuIFIgKDEgJmx0Oz0gUiAmbHQ7PSAyLDUwMCkgdW5pdHMgZnJvbSBoZXIuPFwvcD5cclxuXHJcbjxwPkJlc3NpZSBoYXMgYSBzaGllbGQgdG8gcHJvdGVjdCBoZXJzZWxmIGZyb20gdGhlc2UgYXR0YWNrcy4gSG93ZXZlciwgc2hlIGRvZXMgbm90IHdhbnQgdG8gd2FzdGUgYW55IG9mIGhlciBzaGllbGQmIzM5O3MgcG93ZXIsIHNvIHNoZSB3b3VsZCBsaWtlIHRvIGtub3cgdGhlIG1heGltdW0gbnVtYmVyIG9mIGNhdHRsZSBicnVpc2VycyB3aXRoaW4gZmlyaW5nIHJhbmdlIGZvciBhbnkgKHBvdGVudGlhbGx5IG5vbi1pbnRlZ2VyKSB0aW1lIHQgJmd0Oz0gMC48XC9wPlxyXG5cclxuPHA+SW4gb3JkZXIgdG8gYXZvaWQgcHJlY2lzaW9uIGVycm9ycyB3aXRoIHJlYWwgbnVtYmVycywgaXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSBhbnN3ZXIgcHJvZHVjZWQgd2lsbCBiZSB0aGUgc2FtZSB3aGV0aGVyIHRoZSBhdHRhY2sgcmFuZ2UgaXMgZGVjcmVhc2VkIHRvIFItMC4wMDAxIG9yIGluY3JlYXNlZCB0byBSKzAuMDAwMS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBTaXggc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOLCBSLCBCWCwgQlksIEJWWCwgYW5kIEJWWTxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgZm91ciBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IFhfaSwgWV9pLCBWWF9pLCBhbmQgVllfaTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBQcmludCBhIHNpbmdsZSBpbnRlZ2VyIGRlbm90aW5nIHRoZSBtYXhpbXVtIG51bWJlciBvZiBjYXR0bGUgYnJ1aXNlcnMgd2l0aGluIGF0dGFjayByYW5nZSBhdCBhbnkgcG9pbnQgaW4gdGltZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d