충전소 저장 장치의 하루

문제

한 전기차 충전소에는 전기를 임시로 보관하는 저장 장치가 있다. 저장 장치에 들어 있는 전기는 충전소가 정한 정수 단위로 기록하며, 장치에는 최대 C단위까지 저장할 수 있다. 하루를 시작할 때 장치에는 S단위의 전기가 들어 있다. 충전소는 이후 N번의 작업을 입력에 주어진 순서대로 처리한다. 각 작업에서는 먼저 외부 전력망으로부터 A단위의 전기를 저장 장치에 넣으려고 한다. 현재 저장량과 A의 합이 C 이하라면 들어온 전기를 전부 저장한다. 그 합이 C보다 크다면 저장량이 C가 될 때까지만 받아들이고, 나머지는 받지 못한 전기로 기록한다. 이렇게 받지 못한 전기는 저장 장치에 남지 않으며 이후 작업에서 다시 사용할 수도 없다. 전기를 받는 과정이 끝나면, 같은 작업에서 차량들이 총 B단위의 전기를 요청한다. 저장 장치에 B단위 이상이 있으면 정확히 B단위를 공급한다. 저장량이 B보다 작으면 남아 있는 전기를 모두 공급하여 저장량이 0이 된다. 공급하지 못한 요청량은 다음 작업으로 넘기지 않는다. 외부 전기를 받는 과정과 차량에 공급하는 과정의 순서는 모든 작업에서 동일하다. 운영자는 모든 작업이 끝났을 때 장치에 남은 전기와, 하루 동안 용량 부족으로 받지 못한 전기의 합을 확인하려 한다. 차량에 공급하지 못한 양은 이 합에 포함하지 않는다. 저장 장치에서는 설명한 작업 외에 전기가 추가되거나 줄어들지 않는다. 같은 수치의 작업이 여러 번 주어져도 각각 별도의 작업으로 처리한다. 마지막 저장량과 받지 못한 전기의 총량을 계산하라.

입력

첫째 줄에 정수 N, C, S가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000, 0 ≤ S ≤ C이다. 다음 N개 줄에는 각 작업의 정수 A, B가 공백으로 구분되어 주어진다. 0 ≤ A, B ≤ 1,000이다. 작업은 입력 순서대로 수행한다.

출력

모든 작업이 끝난 뒤의 저장량과 용량 부족으로 받지 못한 전기의 총량을 한 줄에 공백으로 구분하여 출력한다. 받지 못한 전기가 없으면 두 번째 값으로 0을 출력한다.

3 10 4
9 3
2 8
7 1

7 3

2 5 0
0 4
3 8

0 0

3 6 6
6 0
6 0
6 0

6 18

출처: Devin.KR 자체 제작