마지막 칸의 승차 기록

문제

지하철의 마지막 칸에는 최대 C명까지 탈 수 있다. 이 칸의 혼잡도를 조사하기 위해 열차가 출발역을 떠나기 직전부터 마지막 조사역에서 문을 닫을 때까지 승객 수를 기록하려 한다. 출발역을 떠나기 직전에 타고 있는 승객은 S명이며, 이후 열차는 조사 대상인 N개 역을 입력에 주어진 순서대로 지난다. 각 조사역에는 하차 안내 인원 A와 승차 대기 인원 B가 기록되어 있다. 하차 안내 인원은 실제 하차 인원을 확정한 값이 아니라, 해당 역의 안내 장치가 내보낸 요청 인원이다. 따라서 열차에 타고 있는 승객 수가 A보다 적으면 현재 승객 전원이 내리고, 그렇지 않으면 정확히 A명이 내린다. 이 과정에서 승객 수가 음수가 되는 일은 없다. 하차가 모두 끝나면 승차를 진행한다. 대기 중인 B명은 빈자리가 허용하는 만큼만 타며, 정원에 도달한 뒤 남은 사람은 그 역에서 승차하지 못한다. 승차하지 못한 사람은 다음 조사역의 대기 인원에 합쳐지지 않는다. 각 역의 B는 앞선 역의 처리 결과와 관계없이 그 역에서 새로 주어진 인원이다. 하차와 승차는 반드시 이 순서로 한 번씩만 처리한다. 조사자는 모든 조사역의 처리가 끝난 뒤 칸에 남은 승객 수, 전체 조사 구간에서 승차하지 못한 인원의 합, 그리고 문을 닫는 순간의 승객 수가 정원 C와 같았던 조사역의 수를 알고 싶다. 한 역에서 내린 직후에는 정원보다 적었더라도 승차를 마친 뒤 정원이 되었다면 그 역을 센다. 출발역은 이 역의 수에 포함하지 않는다. 같은 사람이 다른 역에 다시 나타나는 상황은 고려하지 않으며, 승차하지 못한 인원은 각 역의 수치를 그대로 합한다. 세 값을 계산하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, C, S가 공백으로 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ C ≤ 100,000, 0 ≤ S ≤ C다. 다음 N개 줄에는 조사역 순서대로 정수 A, B가 공백으로 주어진다. 0 ≤ A, B ≤ 100,000이다. 모든 인원과 역의 수는 정수다.

출력

마지막 조사역에서 승차를 마친 뒤의 승객 수, 승차하지 못한 인원의 총합, 승차를 마친 뒤 정원이었던 조사역의 수를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 해당 인원이나 역이 없으면 그 값으로 0을 출력한다.

4 10 4
2 9
3 1
20 2
0 12

10 5 2

3 5 0
0 0
8 0
0 0

0 0 0

출처: Devin.KR 자체 제작