천문대의 완성된 관측 묶음

문제

한 천문대가 여러 밤에 걸쳐 같은 방식으로 하늘을 관측한다. 관측 장비는 정확히 K분 동안 연속으로 작동해야 하나의 관측 묶음을 완성한다. 천문대의 담당자는 각 밤에 장비를 사용할 수 있는 시간이 정해져 있을 때, 모든 밤을 통틀어 완성할 수 있는 관측 묶음의 개수를 계산하려 한다. 관측하는 밤은 모두 N번이다. i번째 밤에는 장비를 D_i분 동안 사용할 수 있지만, 먼저 장비를 준비하는 데 P_i분이 걸린다. 준비하는 동안에는 관측을 진행할 수 없다. 준비는 매일 밤 반드시 새로 해야 하므로, 이전 밤에 준비를 마쳤더라도 다음 밤의 준비 시간을 줄일 수 없다. 준비가 끝나면 그날 밤에 남아 있는 시간을 모두 관측에 사용한다. 하나의 묶음이 완성되면 곧바로 다음 묶음의 관측을 시작할 수 있다. 묶음 사이에 별도의 정리 시간이나 대기 시간은 들지 않는다. 남은 시간이 정확히 K분이면 묶음을 하나 더 완성할 수 있다. 반면 남은 시간이 K분보다 짧으면 그 시간으로는 새로운 묶음을 완성할 수 없다. 사용할 수 있는 시간이 준비 시간과 같아서 관측 시간이 전혀 남지 않는 밤도 있을 수 있다. 각 관측 묶음은 반드시 같은 밤 안에 시작하고 끝내야 한다. 어떤 밤에 끝내지 못한 관측을 다음 밤에 이어서 진행하거나, 여러 밤에 남은 짧은 시간을 합쳐 하나의 묶음으로 만드는 것은 허용되지 않는다. 따라서 매일 밤 완성한 묶음만 그날의 실적으로 기록한다. 묶음에 별도의 우선순위나 점수 차이는 없고, 완성된 묶음 하나를 항상 1개로 센다. 각 밤의 사용 가능 시간과 준비 시간이 주어질 때, N번의 밤 동안 완성할 수 있는 관측 묶음의 총개수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 관측하는 밤의 수 N과 관측 묶음 하나에 필요한 시간 K가 공백으로 구분되어 주어진다. 다음 N개의 줄 중 i번째 줄에 D_i와 P_i가 공백으로 구분되어 주어진다. 모든 입력값은 정수이며, 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000, 0 ≤ P_i ≤ D_i ≤ 1,000이다. 모든 시간의 단위는 분이다.

출력

모든 밤에 완성할 수 있는 관측 묶음의 총개수를 정수 하나로 출력한다. 완성할 수 있는 묶음이 하나도 없으면 0을 출력한다.

3 7
30 5
20 6
10 4

5

2 10
9 0
15 6

0

3 4
12 0
8 8
17 1

7

출처: Devin.KR 자체 제작