보급소까지 달리기

문제

마라톤 대회에서 한 참가자가 보급소를 차례대로 지나가는 훈련을 한다. 훈련 코스에는 출발점 이후 N개의 보급소가 있고, 가까운 보급소부터 1번부터 N번까지 번호가 붙어 있다. 참가자는 보급소를 건너뛰거나 이미 지나온 보급소로 돌아갈 수 없다. 이번 훈련에서는 달린 거리 대신 체력의 변화만을 기록한다. 참가자가 가질 수 있는 체력의 최댓값은 C이고, 출발할 때의 체력도 C이다. i번 보급소의 기록에는 직전 지점에서 해당 보급소까지 달리는 데 필요한 체력 D_i와 도착한 뒤 보충할 수 있는 체력 R_i가 적혀 있다. 1번 보급소의 직전 지점은 출발점이며, 나머지 보급소의 직전 지점은 바로 앞 번호의 보급소이다. 참가자는 다음 보급소로 출발하기 전에 현재 체력을 확인한다. 현재 체력이 그 구간에 필요한 체력 이상이면 구간을 완주하고, 현재 체력에서 필요한 체력을 뺀다. 도착한 보급소는 이때 방문한 것으로 센다. 이어서 해당 보급소의 보충량을 현재 체력에 더한다. 더한 결과가 C보다 크면 현재 체력을 C로 바꾼다. 보충량을 일부 남겨 두었다가 나중에 사용하는 것은 불가능하다. 현재 체력이 다음 구간에 필요한 체력보다 작으면 참가자는 즉시 훈련을 끝낸다. 그 보급소와 그 뒤의 보급소는 방문하지 못한 것으로 처리한다. 필요한 체력과 현재 체력이 같으면 정상적으로 도착할 수 있으며, 도착 직후 체력이 0이 되어도 해당 보급소에서 보충받을 수 있다. 모든 보급소에 도착했다면 훈련은 N번 보급소에서 끝난다. 주어진 기록에 따라 참가자가 방문하는 보급소의 개수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 보급소의 개수 N과 최대 체력 C가 공백으로 구분되어 주어진다. 다음 N개의 줄 중 i번째 줄에 D_i와 R_i가 공백으로 구분되어 주어진다. 모든 입력값은 정수이며, 1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000, 1 ≤ D_i ≤ 1,000, 0 ≤ R_i ≤ 1,000이다. 보급소 기록은 방문 순서대로 주어진다.

출력

방문한 보급소의 개수를 정수 하나로 출력한다. 첫 번째 보급소에도 도착하지 못하면 0을 출력하고, 모두 방문하면 N을 출력한다.

4 10
6 3
7 9
9 0
1 0

3

2 3
4 10
1 0

0

3 5
5 5
5 5
5 0

3

출처: Devin.KR 자체 제작