시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 77 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

힌트

W3sicHJvYmxlbV9pZCI6IjMzMjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWM5YzQiLCJkZXNjcmlwdGlvbiI6IjxwPklQU0MgU2Vjb25kYXJ5IDlcdWI0ZjFcdWM1ZDAgXHViZTViXHViMDk4XHViMjk0IFx1YzgxNVx1YmNmNFx1YzYwMVx1YzdhYywgXHVjNzI0XHVjOWMwXHVjNmE5XHVjNzU4IFx1Y2RlOFx1YmJmOFx1YWMwMCBcdWMwYWNcdWM5YzRcdWNjMGRcdWFlMzBcdWM3NzggXHVhYzgzXHVjNzQwIFx1Yzc5OCBcdWM1NGNcdWI4MjRcdWM5YzQgXHVjMGFjXHVjMmU0XHVjNzc0XHViMmU0LiBcdWM5YzBcdWM2YTlcdWM3NzRcdWIyOTQgXHVkNTU4XHViMjk4XHVjNWQwIFx1Yzc4OFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YmNjNFx1Yzc0NCBcdWNjMGRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1Y2U3NFx1YmE1NFx1Yjc3Y1x1Yjk3YyBcdWFlYmNcdWIwYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YzZhOVx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1Y2U3NFx1YmE1NFx1Yjc3Y1x1YjI5NCwgXHVhYzAwXHViODVjIFx1YzEzOFx1Yjg1YyBcdWJlNDRcdWM3MjhcdWM1ZDAgXHVjMGMxXHVhZDAwXHVjNWM2XHVjNzc0IFx1YjExM1x1Yzc3NCBBXHVjNzc4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NTggXHVjMGFjXHVjOWM0XHVjNzQ0IFx1ZDU2ZFx1YzBjMSBcdWNjMGRcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjLCBcdWQzYjhcdWM5ZDFcdWM3NDQgXHVkM2I4XHViOWFjXHVkNTU4XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMsIFx1YzljMFx1YzZhOVx1Yzc3NFx1YWMwMCBcdWNjMGRcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDYxNVx1ZDBkY1x1Yzc1OCBcdWMwYWNcdWM5YzRcdWM3NDAgXHVjODhjXHVkNDVjXHVjZDk1XHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIHhcdWNkOTVcdWFjZmMgXHViYzExXHViY2MwXHVjNzc0IFx1YmQ5OVx1YzViNFx1Yzc4OFx1YzViNFx1YzU3Y1x1YjljYyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjMWNcdWM3NTggXHViY2M0XHVjNzQwIFx1YzgxNVx1YzIxOCBcdWM4OGNcdWQ0NWMgKHgsIHkpXHViODVjIFx1YjMwMFx1ZDQ1Y1x1YjQxOFx1YjI5NFx1YjM3MCwgXHVjOWMwXHVjNmE5XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWMwYWNcdWM5YzQgXHVhYzFjXHVjMjE4XHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YzVlYyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYWE4XHViNGUwIFx1YmNjNFx1Yzc0NCBcdWNjMGRcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LiBcdWNkNWNcdWMxOGNcdWM3NTggXHVjMGFjXHVjOWM0IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjYzRcdWM3NTggXHVjMjE4IE5cdWFjZmMsIFx1YzBhY1x1YzljNFx1Yzc1OCBcdWIxMTNcdWM3NzQgQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIEFcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiAoMSZuYnNwOyZsZTsgTiZuYnNwOyZsZTsgMTAwLCAxJm5ic3A7JmxlOyBBJm5ic3A7JmxlOyAyMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViY2M0XHVjNzU4IFx1Yzg4Y1x1ZDQ1YyAoeCwgeSlcdWFjMDAgXHVjODE1XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YzgxMFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVjODhjXHVkNDVjXHViOTdjIFx1YWMwMFx1YzljMFx1YzljMFx1YjI5NCBcdWM1NGFcdWIyOTRcdWIyZTQuICgwJm5ic3A7JmxlOyB4Jm5ic3A7JmxlOyAzLDAwMCwwMDAsIDEmbmJzcDsmbGU7IHkmbmJzcDsmbGU7IEEpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjYzBkXHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGNcdWM3NTggXHVjMGFjXHVjOWM0IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzMzMjBcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTU2cHg7IHdpZHRoOjI2NHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzIwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoicGhvdG8iLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYSBwaG90byBvZiB0aGUgc2t5bGluZSBvZiBUJmFjaXJjO3JndS1NdXJlXHUwMTVmIHRha2VuIGR1cmluZyB0aGUgbmlnaHQuIFNvbWUgcm9vbXMgc3RpbGwgaGF2ZSB0aGUgbGlnaHQgb24uIFlvdSBrbm93IHRoYXQgYWxsIHRoZSBidWlsZGluZ3MgY2FuIGJlIG1vZGVsZWQgYnkgcmVjdGFuZ2xlcyBvZiBzdXJmYWNlIGFyZWEgYXQgbW9zdCBBLiBGaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBidWlsZGluZ3MgdGhhdCBjYW4gbGVhZCB0byB0aGUgcGljdHVyZS48XC9wPlxyXG5cclxuPHA+U3BlY2lmaWNhbGx5LCB5b3UgYXJlIGdpdmVuIGFuIGludGVnZXIgQSwgYW5kIE4gcG9pbnRzIGF0IGludGVnZXIgY29vcmRpbmF0ZXMgKHgseSkuIFlvdSBtdXN0IGZpbmQgYSBtaW5pbXVtIG51bWJlciBvZiByZWN0YW5nbGVzIHRoYXQgaGF2ZSBvbmUgc2lkZSBvbiB0aGUgeC1heGlzIGFuZCBhcmVhIGF0IG1vc3QgQSwgd2hpY2ggY292ZXIgYWxsIHBvaW50cy4gVGhlIHJlY3RhbmdsZXMgbWF5IG92ZXJsYXAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgd2lsbCBjb250YWluIHR3byBpbnRlZ2VycyBOIGFuZCBBLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSBuZXh0IE4gbGluZXMgd2lsbCBjb250YWluIHR3byBpbnRlZ2VycyB4IGFuZCB5LCByZXByZXNlbnRpbmcgdGhlIGNvb3JkaW5hdGVzIG9mIGVhY2ggcG9pbnQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyAxMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IEEgJmxlOyAyMDAgMDAwPFwvbGk+XHJcblx0PGxpPkVhY2ggcG9pbnQgaGFzIDAgJmxlOyB4ICZsZTsgMyAwMDAgMDAwIGFuZCAxICZsZTsgeSAmbGU7IEE8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBzdGFuZGFyZCBvdXRwdXQgc2hvdWxkIGNvbnNpc3Qgb2YgZXhhY3RseSBvbmUgbGluZSBjb250YWluaW5nIHRoZSBtaW5pbXVtIG51bWJlciBvZiByZWN0YW5nbGVzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8zMzIwXC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1NnB4OyB3aWR0aDoyNjRweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d