농장의 아침 물통

문제

한 농장에서는 작은 물통에 저장한 물로 매일 아침 모종에 물을 준다. 물통에는 최대 C만큼의 물을 담을 수 있으며, 관찰을 시작하기 직전에는 S만큼의 물이 들어 있다. 농장 관리자는 앞으로 N일 동안 물통의 상태를 기록하려고 한다. 물의 양은 모두 같은 단위로 나타내며, 이 문제에서 사용하는 모든 양은 정수다. 하루의 작업은 물 보충과 물주기의 순서로 진행한다. 먼저 그날 준비한 물 A만큼을 물통에 붓는다. 기존 물과 보충한 물의 합이 물통의 최대 용량 C를 넘으면 넘친 물은 모두 흘려보내고, 물통에는 정확히 C만큼만 남긴다. 넘친 물을 따로 저장하거나 그날의 물주기에 직접 사용하는 일은 없다. 보충한 양이 0이면 물통에 있던 물의 양은 그대로다. 보충을 마친 뒤에는 그날 필요한 물 B만큼을 물통에서 꺼내려고 한다. 물통에 B 이상이 있으면 정확히 B만큼을 꺼내 모종에 주고, 그날의 물주기를 성공한 것으로 기록한다. 물통에 B보다 적게 있으면 그날의 물주기는 건너뛴다. 이 경우 물을 조금만 주는 일은 없으며, 물통에 들어 있는 물은 전혀 줄어들지 않는다. 건너뛴 날에 필요했던 물을 다음 날 추가로 주지도 않는다. 이 과정이 끝났을 때 남은 물은 다음 날 아침까지 그대로 보관된다. 증발이나 누수는 없고, 입력에 적힌 보충과 물주기 이외에는 물의 양이 변하지 않는다. 매일의 성공 여부는 그날 보충까지 끝난 물의 양으로 판단해야 한다. 물의 양이 필요한 양과 정확히 같다면 물주기에 성공하고 물통은 비게 된다. N일의 작업을 순서대로 처리했을 때 물주기에 성공한 날의 수와 마지막 날 작업 직후 물통에 남은 양을 구한다. 성공한 날이 없다면 성공한 날의 수는 0으로 출력한다.

입력

첫째 줄에 관찰 일수 N, 물통의 최대 용량 C, 초기 물의 양 S가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000, 0 ≤ S ≤ C이다. 다음 N개 줄에는 날짜 순서대로 그날 보충할 양 A와 물주기에 필요한 양 B가 주어진다. 0 ≤ A ≤ 1,000, 1 ≤ B ≤ C이다. 입력의 모든 수는 정수다.

출력

물주기에 성공한 날의 수와 N일째 작업 직후 물통에 남은 양을 공백으로 구분하여 한 줄에 출력한다.

4 10 3
4 5
0 3
12 8
1 3

3 0

3 5 0
1 4
1 4
1 4

0 3

2 7 7
5 7
0 1

1 0

출처: Devin.KR 자체 제작