시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB47601742134337.368%

문제

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1 <= N <= 10,000) 개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이 L (L은 양의 정수) 짜리 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

입력

첫째 줄에 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0이상 1,000,000,000이하의 정수이다.

출력

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

예제 입력 1

3 3
1 6
13 17
8 12

예제 출력 1

5

힌트

아래와 같이 5개의 널빤지가 필요하다.

111222..333444555.... // 길이 3인 널빤지
.MMMMM..MMMM.MMMM.... // 웅덩이
012345678901234567890 // 좌표
W3sicHJvYmxlbV9pZCI6IjE5MTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3NTlcdWFlMzggXHViY2Y0XHVjMjE4XHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWM4MmZcdWJjMjQgXHVhY2E4XHVjNmI4IFx1Y2VhMFx1ZDUwNCBcdWM3YTVcdWMxOGNcdWM1ZDBcdWMxMWMgXHVjNmQ0XHViNGRjIFx1YmNmOFx1YzZkMFx1YWU0Y1x1YzljMCBcdWM3NzRcdWM1YjRcdWM5YzBcdWIyOTQsIFx1ZDc1OVx1YzczY1x1Yjg1YyBcdWI0MWMgXHViZTQ0XHViYzAwXHVhZTM4IFx1YzcwNFx1YzVkMCBcdWQzZWRcdWM2YjBcdWFjMDAgXHViMGI0XHViODI0XHVjMTFjIE4gKDEgJmx0Oz0gTiAmbHQ7PSAxMCwwMDApIFx1YWMxY1x1Yzc1OCBcdWJiM2NcdWM2YzVcdWIzNjlcdWM3NzRcdWFjMDAgXHVjMGRkXHVhY2JjXHViMmU0LiBcdWM2ZDRcdWI0ZGNcdWQ1NTlcdWM2ZDBcdWM3NDAgXHViYjNjXHVjNmM1XHViMzY5XHVjNzc0XHViOTdjIFx1YjM2ZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWUzOFx1Yzc3NCBMIChMXHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTgpIFx1YzlkY1x1YjlhYyBcdWIxMTBcdWJlNjRcdWM5YzBcdWI0ZTRcdWM3NDQgXHVjZGE5XHViZDg0XHVkNzg4IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM1YjRcdWMxMWMsIFx1Yzc3NFx1YjRlNFx1Yjg1YyBcdWIyZTRcdWI5YWNcdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0IFx1YmIzY1x1YzZjNVx1YjM2OVx1Yzc3NFx1YjRlNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViMzZlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYjNjXHVjNmM1XHViMzY5XHVjNzc0XHViNGU0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWQwNmNcdWFlMzBcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViYjNjXHVjNmM1XHViMzY5XHVjNzc0XHViNGU0XHVjNzQ0IFx1YjM2ZVx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YjExMFx1YmU2NFx1YzljMFx1YjRlNFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBMXHVjNzc0IFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIFx1Y2QxZCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjNmM1XHViMzY5XHVjNzc0XHViNGU0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzZjNVx1YjM2OVx1Yzc3NFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgXHVjNmM1XHViMzY5XHVjNzc0XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNThcdWM2NDAgXHViMDVkIFx1YzcwNFx1Y2U1OFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM3MDRcdWNlNThcdWIyOTQgMFx1Yzc3NFx1YzBjMSAxLDAwMCwwMDAsMDAwXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWJiM2NcdWM2YzVcdWIzNjlcdWM3NzRcdWI0ZTRcdWM3NDQgXHViMzZlXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViMTEwXHViZTY0XHVjOWMwXHViNGU0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IDVcdWFjMWNcdWM3NTggXHViMTEwXHViZTY0XHVjOWMwXHVhYzAwIFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuMTExMjIyLi4zMzM0NDQ1NTUuLi4uIFwvXC8gXHVhZTM4XHVjNzc0IDNcdWM3NzggXHViMTEwXHViZTY0XHVjOWMwXHJcbi5NTU1NTS4uTU1NTS5NTU1NLi4uLiBcL1wvIFx1YzZjNVx1YjM2OVx1Yzc3NFxyXG4wMTIzNDU2Nzg5MDEyMzQ1Njc4OTAgXC9cLyBcdWM4OGNcdWQ0NWM8XC9wcmU+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTkxMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik11ZGR5IHJvYWRzIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBoYXMgYSBwcm9ibGVtOiB0aGUgZGlydCByb2FkIGZyb20gaGlzIGZhcm0gdG8gdG93biBoYXMgc3VmZmVyZWQgaW4gdGhlIHJlY2VudCByYWluc3Rvcm1zIGFuZCBub3cgY29udGFpbnMgKDEgJmx0Oz0gTiAmbHQ7PSAxMCwwMDApIG11ZCBwb29scy48XC9wPlxyXG5cclxuPHA+RmFybWVyIEpvaG4gaGFzIGEgY29sbGVjdGlvbiBvZiB3b29kZW4gcGxhbmtzIG9mIGxlbmd0aCBMIHRoYXQgaGUgY2FuIHVzZSB0byBicmlkZ2UgdGhlc2UgbXVkIHBvb2xzLiBIZSBjYW4gb3ZlcmxhcCBwbGFua3MgYW5kIHRoZSBlbmRzIGRvIG5vdCBuZWVkIHRvIGJlIGFuY2hvcmVkIG9uIHRoZSBncm91bmQuIEhvd2V2ZXIsIGhlIG11c3QgY292ZXIgZWFjaCBwb29sIGNvbXBsZXRlbHkuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBtdWQgcG9vbHMsIGhlbHAgRkogZmlndXJlIG91dCB0aGUgbWluaW11bSBudW1iZXIgb2YgcGxhbmtzIGhlIG5lZWRzIGluIG9yZGVyIHRvIGNvbXBsZXRlbHkgY292ZXIgYWxsIHRoZSBtdWQgcG9vbHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgTDxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IExpbmUgaSsxIGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IHNfaSBhbmQgZV9pICgwICZsdDs9IHNfaSAmbHQ7IGVfaSAmbHQ7PSAxLDAwMCwwMDAsMDAwKSB0aGF0IHNwZWNpZnkgdGhlIHN0YXJ0IGFuZCBlbmQgcG9pbnRzIG9mIGEgbXVkIHBvb2wgYWxvbmcgdGhlIHJvYWQuIFRoZSBtdWQgcG9vbHMgd2lsbCBub3Qgb3ZlcmxhcC4gVGhlc2UgbnVtYmVycyBzcGVjaWZ5IHBvaW50cywgc28gYSBtdWQgcG9vbCBmcm9tIDM1IHRvIDM5IGNhbiBiZSBjb3ZlcmVkIGJ5IGEgc2luZ2xlIGJvYXJkIG9mIGxlbmd0aCA0LiBNdWQgcG9vbHMgYXQgKDMsNikgYW5kICg2LDkpIGFyZSBub3QgY29uc2lkZXJlZCB0byBvdmVybGFwLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRoZSBtaW1pbnVtIG51bWJlciBvZiBwbGFua3MgRkogbmVlZHMgdG8gdXNlLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IjxwPkZKIG5lZWRzIHRvIHVzZSBwbGFua3Mgb2YgbGVuZ3RoIDMgdG8gY292ZXIgMyBtdWQgcG9vbHMuIFRoZSBtdWQgcG9vbHMgY292ZXIgcmVnaW9ucyAxIHRvIDYsIDggdG8gMTIsIGFuZCAxMyB0byAxNy48XC9wPlxyXG5cclxuPHA+RkogY2FuIGNvdmVyIHRoZSBtdWQgcG9vbHMgd2l0aCBmaXZlIHBsYW5rcyBvZiBsZW5ndGggMyBpbiB0aGUgZm9sbG93aW5nIHdheTo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgICAgICAgIDExMTIyMi4uMzMzNDQ0NTU1Li4uLlxyXG4gICAgICAgICAgICAgICAgICAgLk1NTU1NLi5NTU1NLk1NTU0uLi4uXHJcbiAgICAgICAgICAgICAgICAgICAwMTIzNDU2Nzg5MDEyMzQ1Njc4OTA8XC9wcmU+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==