시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVjNzg1XHViODI1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0IDombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM1ZjBcdWFkNmNcdWM2ZDBcdWM3NTggXHVjMjE4IG4gKDEgJmxlOyBuICZsZTsgMzAwIDAwMCksIFx1YzZjY1x1ZDA2Y1x1YzJhNFx1ZDE0Y1x1Yzc3NFx1YzE1OFx1Yzc3NCBcdWM3OTBcdWIzZDlcdWM3M2NcdWI4NWMgXHVjN2EwXHVhZTMwXHViMjk0IFx1YWUzMFx1YzkwMCBcdWMyZGNcdWFjMDQgbSAoMSAmbGU7IG0gJmxlOyAxMDxzdXA+ODxcL3N1cD4pIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPm5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIGFcdWM2NDAgc1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgYSwgcyAmbGU7IDEwPHN1cD44PFwvc3VwPikgXHVjNWYwXHVhZDZjXHVjNmQwXHViNGU0XHVjNzQwIGFcdWJkODRcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTc0XHVjMTFjLCBcdWM4MTVcdWQ2NTVcdWQ3ODggc1x1YmQ4NFx1YjNkOVx1YzU0OCBcdWJhMzhcdWJiMzRcdWI5NzhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjMmNcdWMxOTRcdWM3NzRcdWFjMDAgXHVjODA4XHVjNTdkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjN2EwXHVhZTA4IFx1ZDU3NFx1YzgxYyBcdWQ2OWZcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTY2NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFzc2lnbmluZyBXb3Jrc3RhdGlvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPlBlbmVsb3BlIGlzIHBhcnQgb2YgdGhlIGFkbWluIHRlYW0gb2YgdGhlIG5ld2x5IGJ1aWx0IHN1cGVyY29tcHV0ZXIuIEhlciBqb2IgaXMgdG8gYXNzaWduIHdvcmtzdGF0aW9ucyB0byB0aGUgcmVzZWFyY2hlcnMgd2hvIGNvbWUgaGVyZSB0byBydW4gdGhlaXIgY29tcHV0YXRpb25zIGF0IHRoZSBzdXBlcmNvbXB1dGVyLjxcL3A+XHJcblxyXG48cD5QZW5lbG9wZSBpcyB2ZXJ5IGxhenkgYW5kIGhhdGVzIHVubG9ja2luZyBtYWNoaW5lcyBmb3IgdGhlIGFycml2aW5nIHJlc2VhcmNoZXJzLiBTaGUgY2FuIHVubG9jayB0aGUgbWFjaGluZXMgcmVtb3RlbHkgZnJvbSBoZXIgZGVzaywgYnV0IGRvZXMgbm90IGZlZWwgdGhhdCB0aGlzIG1lbmlhbCB0YXNrIG1hdGNoZXMgaGVyIHF1YWxpZmljYXRpb25zLiBTaG91bGQgc2hlIGRlY2lkZSB0byBpZ25vcmUgdGhlIHNlY3VyaXR5IGd1aWRlbGluZXMgc2hlIGNvdWxkIHNpbXBseSBhc2sgdGhlIHJlc2VhcmNoZXJzIG5vdCB0byBsb2NrIHRoZWlyIHdvcmtzdGF0aW9ucyB3aGVuIHRoZXkgbGVhdmUsIGFuZCB0aGVuIGFzc2lnbiBuZXcgcmVzZWFyY2hlcnMgdG8gd29ya3N0YXRpb25zIHRoYXQgYXJlIG5vdCB1c2VkIGFueSBtb3JlIGJ1dCB0aGF0IGFyZSBzdGlsbCB1bmxvY2tlZC4gVGhhdCB3YXksIHNoZSBvbmx5IG5lZWRzIHRvIHVubG9jayBlYWNoIHdvcmtzdGF0aW9uIGZvciB0aGUgZmlyc3QgcmVzZWFyY2hlciB1c2luZyBpdCwgd2hpY2ggd291bGQgYmUgYSBodWdlIGltcHJvdmVtZW50IGZvciBQZW5lbG9wZS48XC9wPlxyXG5cclxuPHA+VW5mb3J0dW5hdGVseSwgdW51c2VkIHdvcmtzdGF0aW9ucyBsb2NrIHRoZW1zZWx2ZXMgYXV0b21hdGljYWxseSBpZiB0aGV5IGFyZSB1bnVzZWQgZm9yIG1vcmUgdGhhbiBtIG1pbnV0ZXMuIEFmdGVyIGEgd29ya3N0YXRpb24gaGFzIGxvY2tlZCBpdHNlbGYsIFBlbmVsb3BlIGhhcyB0byB1bmxvY2sgaXQgYWdhaW4gZm9yIHRoZSBuZXh0IHJlc2VhcmNoZXIgdXNpbmcgaXQuIEdpdmVuIHRoZSBleGFjdCBzY2hlZHVsZSBvZiBhcnJpdmluZyBhbmQgbGVhdmluZyByZXNlYXJjaGVycywgY2FuIHlvdSB0ZWxsIFBlbmVsb3BlIGhvdyBtYW55IHVubG9ja2luZ3Mgc2hlIG1heSBzYXZlIGJ5IGFza2luZyB0aGUgcmVzZWFyY2hlcnMgbm90IHRvIGxvY2sgdGhlaXIgd29ya3N0YXRpb25zIHdoZW4gdGhleSBsZWF2ZSBhbmQgYXNzaWduaW5nIGFycml2aW5nIHJlc2VhcmNoZXJzIHRvIHdvcmtzdGF0aW9ucyBpbiBhbiBvcHRpbWFsIHdheT8gWW91IG1heSBhc3N1bWUgdGhhdCB0aGVyZSBhcmUgYWx3YXlzIGVub3VnaCB3b3Jrc3RhdGlvbnMgYXZhaWxhYmxlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggdHdvIGludGVnZXJzIG4gKDEgJmxlOyBuICZsZTsgMzAwIDAwMCksIHRoZSBudW1iZXIgb2YgcmVzZWFyY2hlcnMsIGFuZCBtICgxICZsZTsgbSAmbGU7IDEwPHN1cD44PFwvc3VwPiksIHRoZSBudW1iZXIgb2YgbWludXRlcyBvZiBpbmFjdGl2aXR5IGFmdGVyIHdoaWNoIGEgd29ya3N0YXRpb24gbG9ja3MgaXRzZWxmOzxcL2xpPlxyXG5cdDxsaT5uIGxpbmVzIGVhY2ggd2l0aCB0d28gaW50ZWdlcnMgYSBhbmQgcyAoMSAmbGU7IGEsIHMgJmxlOyAxMDxzdXA+ODxcL3N1cD4pLCByZXByZXNlbnRpbmcgYSByZXNlYXJjaGVyIHRoYXQgYXJyaXZlcyBhZnRlciBhIG1pbnV0ZXMgYW5kIHN0YXlzIGZvciBleGFjdGx5IHMgbWludXRlcy48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbWF4aW11bSBudW1iZXIgb2YgdW5sb2NraW5ncyBQZW5lbG9wZSBtYXkgc2F2ZSBoZXJzZWxmLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==