시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 75 23 17 56.667%

문제

IPSC Secondary 9등에 빛나는 정보영재, 윤지용의 취미가 사진찍기인 것은 잘 알려진 사실이다. 지용이는 하늘에 있는 N개의 별을 찍기 위해 카메라를 꺼냈다.

지용이가 가지고 있는 카메라는, 가로 세로 비율에 상관없이 넓이 A인 직사각형 모양의 사진을 항상 찍을 수 있다. 또한, 편집을 편리하게 하기 위해서, 지용이가 찍는 직사각형 형태의 사진은 좌표축에 평행해야 하고, x축과 밑변이 붙어있어야만 한다.

N개의 별은 정수 좌표 (x, y)로 대표되는데, 지용이는 최소의 사진 개수를 사용하여 주어진 모든 별을 찍고 싶어한다. 최소의 사진 개수를 출력해주자.

입력

첫번째 줄에 별의 수 N과, 사진의 넓이 A가 주어진다. A는 정수이다. (1 ≤ N ≤ 100, 1 ≤ A ≤ 200,000)

이후 N개의 줄에 별의 좌표 (x, y)가 정수로 주어진다. 두 점이 같은 좌표를 가지지는 않는다. (0 ≤ x ≤ 3,000,000, 1 ≤ y ≤ A)

출력

찍어야 하는 최소의 사진 개수를 출력한다.

예제 입력 1

6 4
2 1
4 1
5 1
5 4
7 1
6 4

예제 출력 1

3

힌트

W3sicHJvYmxlbV9pZCI6IjMzMjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWM5YzQiLCJkZXNjcmlwdGlvbiI6IjxwPklQU0MgU2Vjb25kYXJ5IDlcdWI0ZjFcdWM1ZDAgXHViZTViXHViMDk4XHViMjk0IFx1YzgxNVx1YmNmNFx1YzYwMVx1YzdhYywgXHVjNzI0XHVjOWMwXHVjNmE5XHVjNzU4IFx1Y2RlOFx1YmJmOFx1YWMwMCBcdWMwYWNcdWM5YzRcdWNjMGRcdWFlMzBcdWM3NzggXHVhYzgzXHVjNzQwIFx1Yzc5OCBcdWM1NGNcdWI4MjRcdWM5YzQgXHVjMGFjXHVjMmU0XHVjNzc0XHViMmU0LiBcdWM5YzBcdWM2YTlcdWM3NzRcdWIyOTQgXHVkNTU4XHViMjk4XHVjNWQwIFx1Yzc4OFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YmNjNFx1Yzc0NCBcdWNjMGRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1Y2U3NFx1YmE1NFx1Yjc3Y1x1Yjk3YyBcdWFlYmNcdWIwYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YzZhOVx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1Y2U3NFx1YmE1NFx1Yjc3Y1x1YjI5NCwgXHVhYzAwXHViODVjIFx1YzEzOFx1Yjg1YyBcdWJlNDRcdWM3MjhcdWM1ZDAgXHVjMGMxXHVhZDAwXHVjNWM2XHVjNzc0IFx1YjExM1x1Yzc3NCBBXHVjNzc4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NTggXHVjMGFjXHVjOWM0XHVjNzQ0IFx1ZDU2ZFx1YzBjMSBcdWNjMGRcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjLCBcdWQzYjhcdWM5ZDFcdWM3NDQgXHVkM2I4XHViOWFjXHVkNTU4XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMsIFx1YzljMFx1YzZhOVx1Yzc3NFx1YWMwMCBcdWNjMGRcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDYxNVx1ZDBkY1x1Yzc1OCBcdWMwYWNcdWM5YzRcdWM3NDAgXHVjODhjXHVkNDVjXHVjZDk1XHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIHhcdWNkOTVcdWFjZmMgXHViYzExXHViY2MwXHVjNzc0IFx1YmQ5OVx1YzViNFx1Yzc4OFx1YzViNFx1YzU3Y1x1YjljYyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjMWNcdWM3NTggXHViY2M0XHVjNzQwIFx1YzgxNVx1YzIxOCBcdWM4OGNcdWQ0NWMgKHgsIHkpXHViODVjIFx1YjMwMFx1ZDQ1Y1x1YjQxOFx1YjI5NFx1YjM3MCwgXHVjOWMwXHVjNmE5XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWMwYWNcdWM5YzQgXHVhYzFjXHVjMjE4XHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YzVlYyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYWE4XHViNGUwIFx1YmNjNFx1Yzc0NCBcdWNjMGRcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LiBcdWNkNWNcdWMxOGNcdWM3NTggXHVjMGFjXHVjOWM0IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmNjNFx1Yzc1OCBcdWMyMTggTlx1YWNmYywgXHVjMGFjXHVjOWM0XHVjNzU4IFx1YjExM1x1Yzc3NCBBXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gQVx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuICgxJm5ic3A7JmxlOyBOJm5ic3A7JmxlOyAxMDAsIDEmbmJzcDsmbGU7IEEmbmJzcDsmbGU7IDIwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWJjYzRcdWM3NTggXHVjODhjXHVkNDVjICh4LCB5KVx1YWMwMCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHVjODEwXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHVhYzAwXHVjOWMwXHVjOWMwXHViMjk0IFx1YzU0YVx1YjI5NFx1YjJlNC4gKDAmbmJzcDsmbGU7IHgmbmJzcDsmbGU7IDMsMDAwLDAwMCwgMSZuYnNwOyZsZTsgeSZuYnNwOyZsZTsgQSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjMGRcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWMwYWNcdWM5YzQgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMzMyMFwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTZweDsgd2lkdGg6MjY0cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMzMjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJwaG90byIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBhIHBob3RvIG9mIHRoZSBza3lsaW5lIG9mIFQmYWNpcmM7cmd1LU11cmVcdTAxNWYgdGFrZW4gZHVyaW5nIHRoZSBuaWdodC4gU29tZSByb29tcyBzdGlsbCBoYXZlIHRoZSBsaWdodCBvbi4gWW91IGtub3cgdGhhdCBhbGwgdGhlIGJ1aWxkaW5ncyBjYW4gYmUgbW9kZWxlZCBieSByZWN0YW5nbGVzIG9mIHN1cmZhY2UgYXJlYSBhdCBtb3N0IEEuIEZpbmQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGJ1aWxkaW5ncyB0aGF0IGNhbiBsZWFkIHRvIHRoZSBwaWN0dXJlLjxcL3A+XHJcblxyXG48cD5TcGVjaWZpY2FsbHksIHlvdSBhcmUgZ2l2ZW4gYW4gaW50ZWdlciBBLCBhbmQgTiBwb2ludHMgYXQgaW50ZWdlciBjb29yZGluYXRlcyAoeCx5KS4gWW91IG11c3QgZmluZCBhIG1pbmltdW0gbnVtYmVyIG9mIHJlY3RhbmdsZXMgdGhhdCBoYXZlIG9uZSBzaWRlIG9uIHRoZSB4LWF4aXMgYW5kIGFyZWEgYXQgbW9zdCBBLCB3aGljaCBjb3ZlciBhbGwgcG9pbnRzLiBUaGUgcmVjdGFuZ2xlcyBtYXkgb3ZlcmxhcC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCB3aWxsIGNvbnRhaW4gdHdvIGludGVnZXJzIE4gYW5kIEEsIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIG5leHQgTiBsaW5lcyB3aWxsIGNvbnRhaW4gdHdvIGludGVnZXJzIHggYW5kIHksIHJlcHJlc2VudGluZyB0aGUgY29vcmRpbmF0ZXMgb2YgZWFjaCBwb2ludC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDEwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgQSAmbGU7IDIwMCAwMDA8XC9saT5cclxuXHQ8bGk+RWFjaCBwb2ludCBoYXMgMCAmbGU7IHggJmxlOyAzIDAwMCAwMDAgYW5kIDEgJmxlOyB5ICZsZTsgQTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIHN0YW5kYXJkIG91dHB1dCBzaG91bGQgY29uc2lzdCBvZiBleGFjdGx5IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHJlY3RhbmdsZXMuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzMzMjBcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTU2cHg7IHdpZHRoOjI2NHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=