시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 256 MB 130 58 52 50.000%

문제

찬솔이는 최근 새로 만들어진 슈퍼컴퓨터의 관리를 맡고 있다. 그의 업무는, 연구원들이 슈퍼컴퓨터로 계산을 하려 할 때마다 워크스테이션을 연구원들에게 배정해 주는 것이다.

여기까지는 좋은데, 찬솔이는 매우 게을러서 연구원들이 올 때마다 기계를 잠금 해제하는 것을 귀찮아하기 시작했다. 원격 조종도 가능하긴 한데 아무튼 귀찮은 모양이다. 결국 찬솔이는 보안 규정을 무시하고, 연구원들이 떠나기 전에 워크스테이션을 잠그고 떠나지 말아줄 것을 부탁하기로 했다. 이렇게 하면, 새 연구원들이 왔을 때 잠금이 풀린 빈 워크스테이션에 배정해주면 되니까, 훨씬 일이 덜 귀찮아질 것이다.

애석하게도, 빈 워크스테이션은 m분을 초과하는 시간동안 작업이 없을 때, 자동으로 잠겨진다. 즉 찬솔이가 귀찮게 다시 잠금을 풀어야 한다는 것을 뜻한다. 찬솔이는 각각의 연구원들의 슈퍼컴퓨터 사용 스케줄을 모두 가지고 있다. 찬솔이가 최적의 방법을 사용해서 워크스테이션을 배정한다면, 잠금 해제를 몇번 덜 할 수 있을까? 워크스테이션은 충분하다고 가정해도 괜찮다.

입력

입력은 다음과 같이 주어진다 : 

  • 첫번째 줄에 연구원의 수 n (1 ≤ n ≤ 300 000), 워크스테이션이 자동으로 잠기는 기준 시간 m (1 ≤ m ≤ 108) 이 주어진다. 
  • n개의 줄에 a와 s가 주어진다. (1 ≤ a, s ≤ 108) 연구원들은 a분에 도착해서, 정확히 s분동안 머무른다.

출력

찬솔이가 절약할 수 있는 잠금 해제 횟수의 최댓값을 출력하라.

예제 입력 1

3 5
1 5
6 3
14 6

예제 출력 1

2

예제 입력 2

5 10
2 6
1 2
17 7
3 9
15 6

예제 출력 2

3
W3sicHJvYmxlbV9pZCI6IjExNjY2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNmNjXHVkMDZjXHVjMmE0XHVkMTRjXHVjNzc0XHVjMTU4IFx1YmMzMFx1YzgxNSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjYzJjXHVjMTk0XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YWRmYyBcdWMwYzhcdWI4NWMgXHViOWNjXHViNGU0XHVjNWI0XHVjOWM0IFx1YzI4OFx1ZDM3Y1x1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yzc1OCBcdWFkMDBcdWI5YWNcdWI5N2MgXHViOWUxXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHVjNzU4IFx1YzVjNVx1YmIzNFx1YjI5NCwgXHVjNWYwXHVhZDZjXHVjNmQwXHViNGU0XHVjNzc0IFx1YzI4OFx1ZDM3Y1x1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yjg1YyBcdWFjYzRcdWMwYjBcdWM3NDQgXHVkNTU4XHViODI0IFx1ZDU2MCBcdWI1NGNcdWI5YzhcdWIyZTQgXHVjNmNjXHVkMDZjXHVjMmE0XHVkMTRjXHVjNzc0XHVjMTU4XHVjNzQ0IFx1YzVmMFx1YWQ2Y1x1YzZkMFx1YjRlNFx1YzVkMFx1YWM4YyBcdWJjMzBcdWM4MTVcdWQ1NzQgXHVjOGZjXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHVhZTMwXHVhZTRjXHVjOWMwXHViMjk0IFx1Yzg4Ylx1Yzc0MFx1YjM3MCwgXHVjYzJjXHVjMTk0XHVjNzc0XHViMjk0IFx1YjllNFx1YzZiMCBcdWFjOGNcdWM3NDRcdWI3ZWNcdWMxMWMgXHVjNWYwXHVhZDZjXHVjNmQwXHViNGU0XHVjNzc0IFx1YzYyYyBcdWI1NGNcdWI5YzhcdWIyZTQgXHVhZTMwXHVhY2M0XHViOTdjIFx1YzdhMFx1YWUwOCBcdWQ1NzRcdWM4MWNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWRjMFx1Y2MyZVx1YzU0NFx1ZDU1OFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1ODhcdWIyZTQuIFx1YzZkMFx1YWNhOSBcdWM4NzBcdWM4ODVcdWIzYzQgXHVhYzAwXHViMmE1XHVkNTU4XHVhZTM0IFx1ZDU1Y1x1YjM3MCBcdWM1NDRcdWJiMzRcdWQyYmMgXHVhZGMwXHVjYzJlXHVjNzQwIFx1YmFhOFx1YzU5MVx1Yzc3NFx1YjJlNC4gXHVhY2IwXHVhZDZkIFx1Y2MyY1x1YzE5NFx1Yzc3NFx1YjI5NCBcdWJjZjRcdWM1NDggXHVhZGRjXHVjODE1XHVjNzQ0IFx1YmIzNFx1YzJkY1x1ZDU1OFx1YWNlMCwgXHVjNWYwXHVhZDZjXHVjNmQwXHViNGU0XHVjNzc0IFx1YjVhMFx1YjA5OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHVjNmNjXHVkMDZjXHVjMmE0XHVkMTRjXHVjNzc0XHVjMTU4XHVjNzQ0IFx1YzdhMFx1YWRmOFx1YWNlMCBcdWI1YTBcdWIwOThcdWM5YzAgXHViOWQwXHVjNTQ0XHVjOTA0IFx1YWM4M1x1Yzc0NCBcdWJkODBcdWQwYzFcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTU4XHViYTc0LCBcdWMwYzggXHVjNWYwXHVhZDZjXHVjNmQwXHViNGU0XHVjNzc0IFx1YzY1NFx1Yzc0NCBcdWI1NGMgXHVjN2EwXHVhZTA4XHVjNzc0IFx1ZDQ4MFx1YjliMCBcdWJlNDggXHVjNmNjXHVkMDZjXHVjMmE0XHVkMTRjXHVjNzc0XHVjMTU4XHVjNWQwIFx1YmMzMFx1YzgxNVx1ZDU3NFx1YzhmY1x1YmE3NCBcdWI0MThcdWIyYzhcdWFlNGMsIFx1ZDZlOFx1YzUyYyBcdWM3N2NcdWM3NzQgXHViMzVjIFx1YWRjMFx1Y2MyZVx1YzU0NFx1YzljOCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU2MFx1YzExZFx1ZDU1OFx1YWM4Y1x1YjNjNCwgXHViZTQ4IFx1YzZjY1x1ZDA2Y1x1YzJhNFx1ZDE0Y1x1Yzc3NFx1YzE1OFx1Yzc0MCBtXHViZDg0XHVjNzQ0IFx1Y2QwOFx1YWNmY1x1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWIzZDlcdWM1NDggXHVjNzkxXHVjNWM1XHVjNzc0IFx1YzVjNlx1Yzc0NCBcdWI1NGMsIFx1Yzc5MFx1YjNkOVx1YzczY1x1Yjg1YyBcdWM3YTBcdWFjYThcdWM5YzRcdWIyZTQuIFx1Yzk4OSBcdWNjMmNcdWMxOTRcdWM3NzRcdWFjMDAgXHVhZGMwXHVjYzJlXHVhYzhjIFx1YjJlNFx1YzJkYyBcdWM3YTBcdWFlMDhcdWM3NDQgXHVkNDgwXHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHViNzNiXHVkNTVjXHViMmU0LiBcdWNjMmNcdWMxOTRcdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzVmMFx1YWQ2Y1x1YzZkMFx1YjRlNFx1Yzc1OCBcdWMyODhcdWQzN2NcdWNlZjRcdWQ0ZThcdWQxMzAgXHVjMGFjXHVjNmE5IFx1YzJhNFx1Y2YwMFx1YzkwNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjYzJjXHVjMTk0XHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YzgwMVx1Yzc1OCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTc0XHVjMTFjIFx1YzZjY1x1ZDA2Y1x1YzJhNFx1ZDE0Y1x1Yzc3NFx1YzE1OFx1Yzc0NCBcdWJjMzBcdWM4MTVcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YzdhMFx1YWUwOCBcdWQ1NzRcdWM4MWNcdWI5N2MgXHViYTg3XHViYzg4IFx1YjM1YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz8gXHVjNmNjXHVkMDZjXHVjMmE0XHVkMTRjXHVjNzc0XHVjMTU4XHVjNzQwIFx1Y2RhOVx1YmQ4NFx1ZDU1OFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NzRcdWIzYzQgXHVhZDFjXHVjYzJlXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0IDombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzVmMFx1YWQ2Y1x1YzZkMFx1Yzc1OCBcdWMyMTggbiAoMSAmbGU7IG4gJmxlOyAzMDAgMDAwKSwgXHVjNmNjXHVkMDZjXHVjMmE0XHVkMTRjXHVjNzc0XHVjMTU4XHVjNzc0IFx1Yzc5MFx1YjNkOVx1YzczY1x1Yjg1YyBcdWM3YTBcdWFlMzBcdWIyOTQgXHVhZTMwXHVjOTAwIFx1YzJkY1x1YWMwNCBtICgxICZsZTsgbSAmbGU7IDEwPHN1cD44PFwvc3VwPikgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+blx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgYVx1YzY0MCBzXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBhLCBzICZsZTsgMTA8c3VwPjg8XC9zdXA+KSBcdWM1ZjBcdWFkNmNcdWM2ZDBcdWI0ZTRcdWM3NDAgYVx1YmQ4NFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NzRcdWMxMWMsIFx1YzgxNVx1ZDY1NVx1ZDc4OCBzXHViZDg0XHViM2Q5XHVjNTQ4IFx1YmEzOFx1YmIzNFx1Yjk3OFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2MyY1x1YzE5NFx1Yzc3NFx1YWMwMCBcdWM4MDhcdWM1N2RcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM3YTBcdWFlMDggXHVkNTc0XHVjODFjIFx1ZDY5Zlx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExNjY2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQXNzaWduaW5nIFdvcmtzdGF0aW9ucyIsImRlc2NyaXB0aW9uIjoiPHA+UGVuZWxvcGUgaXMgcGFydCBvZiB0aGUgYWRtaW4gdGVhbSBvZiB0aGUgbmV3bHkgYnVpbHQgc3VwZXJjb21wdXRlci4gSGVyIGpvYiBpcyB0byBhc3NpZ24gd29ya3N0YXRpb25zIHRvIHRoZSByZXNlYXJjaGVycyB3aG8gY29tZSBoZXJlIHRvIHJ1biB0aGVpciBjb21wdXRhdGlvbnMgYXQgdGhlIHN1cGVyY29tcHV0ZXIuPFwvcD5cclxuXHJcbjxwPlBlbmVsb3BlIGlzIHZlcnkgbGF6eSBhbmQgaGF0ZXMgdW5sb2NraW5nIG1hY2hpbmVzIGZvciB0aGUgYXJyaXZpbmcgcmVzZWFyY2hlcnMuIFNoZSBjYW4gdW5sb2NrIHRoZSBtYWNoaW5lcyByZW1vdGVseSBmcm9tIGhlciBkZXNrLCBidXQgZG9lcyBub3QgZmVlbCB0aGF0IHRoaXMgbWVuaWFsIHRhc2sgbWF0Y2hlcyBoZXIgcXVhbGlmaWNhdGlvbnMuIFNob3VsZCBzaGUgZGVjaWRlIHRvIGlnbm9yZSB0aGUgc2VjdXJpdHkgZ3VpZGVsaW5lcyBzaGUgY291bGQgc2ltcGx5IGFzayB0aGUgcmVzZWFyY2hlcnMgbm90IHRvIGxvY2sgdGhlaXIgd29ya3N0YXRpb25zIHdoZW4gdGhleSBsZWF2ZSwgYW5kIHRoZW4gYXNzaWduIG5ldyByZXNlYXJjaGVycyB0byB3b3Jrc3RhdGlvbnMgdGhhdCBhcmUgbm90IHVzZWQgYW55IG1vcmUgYnV0IHRoYXQgYXJlIHN0aWxsIHVubG9ja2VkLiBUaGF0IHdheSwgc2hlIG9ubHkgbmVlZHMgdG8gdW5sb2NrIGVhY2ggd29ya3N0YXRpb24gZm9yIHRoZSBmaXJzdCByZXNlYXJjaGVyIHVzaW5nIGl0LCB3aGljaCB3b3VsZCBiZSBhIGh1Z2UgaW1wcm92ZW1lbnQgZm9yIFBlbmVsb3BlLjxcL3A+XHJcblxyXG48cD5VbmZvcnR1bmF0ZWx5LCB1bnVzZWQgd29ya3N0YXRpb25zIGxvY2sgdGhlbXNlbHZlcyBhdXRvbWF0aWNhbGx5IGlmIHRoZXkgYXJlIHVudXNlZCBmb3IgbW9yZSB0aGFuIG0gbWludXRlcy4gQWZ0ZXIgYSB3b3Jrc3RhdGlvbiBoYXMgbG9ja2VkIGl0c2VsZiwgUGVuZWxvcGUgaGFzIHRvIHVubG9jayBpdCBhZ2FpbiBmb3IgdGhlIG5leHQgcmVzZWFyY2hlciB1c2luZyBpdC4gR2l2ZW4gdGhlIGV4YWN0IHNjaGVkdWxlIG9mIGFycml2aW5nIGFuZCBsZWF2aW5nIHJlc2VhcmNoZXJzLCBjYW4geW91IHRlbGwgUGVuZWxvcGUgaG93IG1hbnkgdW5sb2NraW5ncyBzaGUgbWF5IHNhdmUgYnkgYXNraW5nIHRoZSByZXNlYXJjaGVycyBub3QgdG8gbG9jayB0aGVpciB3b3Jrc3RhdGlvbnMgd2hlbiB0aGV5IGxlYXZlIGFuZCBhc3NpZ25pbmcgYXJyaXZpbmcgcmVzZWFyY2hlcnMgdG8gd29ya3N0YXRpb25zIGluIGFuIG9wdGltYWwgd2F5PyBZb3UgbWF5IGFzc3VtZSB0aGF0IHRoZXJlIGFyZSBhbHdheXMgZW5vdWdoIHdvcmtzdGF0aW9ucyBhdmFpbGFibGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2Y6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCB0d28gaW50ZWdlcnMgbiAoMSAmbGU7IG4gJmxlOyAzMDAgMDAwKSwgdGhlIG51bWJlciBvZiByZXNlYXJjaGVycywgYW5kIG0gKDEgJmxlOyBtICZsZTsgMTA8c3VwPjg8XC9zdXA+KSwgdGhlIG51bWJlciBvZiBtaW51dGVzIG9mIGluYWN0aXZpdHkgYWZ0ZXIgd2hpY2ggYSB3b3Jrc3RhdGlvbiBsb2NrcyBpdHNlbGY7PFwvbGk+XHJcblx0PGxpPm4gbGluZXMgZWFjaCB3aXRoIHR3byBpbnRlZ2VycyBhIGFuZCBzICgxICZsZTsgYSwgcyAmbGU7IDEwPHN1cD44PFwvc3VwPiksIHJlcHJlc2VudGluZyBhIHJlc2VhcmNoZXIgdGhhdCBhcnJpdmVzIGFmdGVyIGEgbWludXRlcyBhbmQgc3RheXMgZm9yIGV4YWN0bHkgcyBtaW51dGVzLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtYXhpbXVtIG51bWJlciBvZiB1bmxvY2tpbmdzIFBlbmVsb3BlIG1heSBzYXZlIGhlcnNlbGYuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d