농장의 하루 물통

문제

한 농장에서는 공용 물통 하나에 물을 모아 두고, 매일 정해진 밭 하나에 물을 준다. 물통의 용량은 C이며 처음에는 물이 S만큼 들어 있다. 물의 양은 모두 정수 단위로 측정한다. 관리 기록에는 앞으로 N일 동안 매일 물통에 들어올 물의 양과 그날 밭에 필요한 물의 양이 적혀 있다. 농장에서는 이 기록을 날짜 순서대로 처리한다. 하루가 시작되면 먼저 그날 들어오는 물을 전부 물통에 붓는다. 이때 물통의 물이 용량 C를 넘으면, 넘친 물은 즉시 흘려보내고 물통에는 정확히 C만큼만 남긴다. 흘려보낸 물은 따로 저장할 수 없으며, 그날이나 이후 날짜에 다시 사용할 수도 없다. 그날 들어오는 물이 0일 수도 있고, 물을 붓기 전부터 물통이 가득 차 있을 수도 있다. 어느 경우든 같은 규칙을 적용한다. 물을 붓고 넘친 물을 처리한 다음에는 그날의 밭에 물을 줄지 결정한다. 물통에 남은 물이 그날 필요한 양 이상이면 필요한 양을 한 번에 꺼내 밭에 주고, 그날을 물주기 성공일로 기록한다. 물통의 물이 필요한 양보다 적으면 그날은 물을 전혀 꺼내지 않는다. 부족한 만큼만 먼저 주거나, 다음 날 들어올 물을 미리 사용하는 일은 없다. 필요한 물의 양이 0이면 물을 꺼내지 않아도 성공일로 센다. 하루의 작업이 끝나면 물통에 남은 물은 그대로 다음 날로 넘어간다. 성공하지 못한 날의 밭에 나중에 다시 물을 주는 일은 없으며, 다음 날에는 다음 기록만 처리한다. 물이 증발하거나 기록에 없는 물이 들어오는 일도 없다. 모든 날의 작업을 마쳤을 때 물주기 성공일의 수, 전체 기간에 흘려보낸 물의 총량, 마지막으로 물통에 남은 물의 양을 구해야 한다. 이 세 값은 실제로 규칙을 적용한 결과를 나타내며, 성공일을 늘리기 위해 작업 순서나 물 사용량을 임의로 바꿀 수는 없다.

입력

첫째 줄에 정수 N, C, S가 공백으로 주어진다. 1 ≤ N ≤ 10,000, 1 ≤ C ≤ 1,000, 0 ≤ S ≤ C이다.
다음 N개 줄 중 i번째 줄에 i일째 들어오는 물의 양 Ri와 그날 필요한 물의 양 Di가 공백으로 주어진다. 0 ≤ Ri, Di ≤ 1,000이다. 필요한 양이 물통의 용량보다 클 수도 있다. 입력에 등장하는 모든 값은 정수다.

출력

물주기 성공일의 수, 흘려보낸 물의 총량, 마지막 날 작업이 끝난 뒤 물통에 남은 물의 양을 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 각 값은 정수로 출력하며, 해당 수량이 없으면 0으로 출력한다.

4 10 3
9 8
1 5
8 6
0 0

3 3 4

3 4 0
2 5
3 5
0 5

0 1 4

1 1 1
0 0

1 0 1

출처: Devin.KR 자체 제작