충전소 저장 장치의 하루

문제

한 전기차 충전소는 전력을 임시로 보관하는 저장 장치를 사용한다. 저장 장치의 최대 용량은 C이며, 영업을 시작할 때는 전력이 S만큼 들어 있다. 이 문제에서는 전력량을 모두 같은 단위의 정수로 나타낸다. 충전소에는 N개의 운영 구간이 있고, 각 구간에서는 외부 전력의 유입과 차량 충전이 정해진 순서로 한 번씩 일어난다. i번째 구간이 시작되면 먼저 외부에서 전력 A_i가 들어온다. 현재 저장된 전력에 A_i를 더한 값이 C 이하라면 들어온 전력을 모두 저장한다. C를 넘는다면 저장량은 C가 되고, 용량을 초과한 나머지는 즉시 버린다. 버린 전력은 이후 구간에서 다시 사용할 수 없다. 전력 유입이 끝난 뒤에는 그 구간에 모인 차량들이 합계 D_i만큼의 전력을 요청한다. 저장된 전력이 요청량 이상이면 차량에 D_i만큼을 공급한다. 저장된 전력이 요청량보다 적으면 남아 있는 전력을 전부 공급한다. 공급한 만큼 저장량이 줄어들며, 충족하지 못한 요청은 해당 구간이 끝날 때 사라진다. 다음 구간에 같은 차량이 다시 요청하는 것으로 처리하거나 부족한 양을 다음 요청에 더하지 않는다. 한 구간에서는 반드시 전력 유입을 먼저 처리하고 차량 충전을 나중에 처리한다. 관리자는 하루 동안 차량에 실제로 공급한 전력의 합과 마지막 구간이 끝난 직후의 저장량을 알고 싶다. 외부에서 들어온 전력의 합이나 차량이 요청한 전력의 합은 실제 공급량과 다를 수 있다. 저장 장치가 가득 차서 전력을 버린 구간과 저장 장치가 비어서 요청을 모두 처리하지 못한 구간도 같은 규칙으로 계산한다. N개 구간을 입력 순서대로 처리하여 두 값을 구한다.

입력

첫째 줄에 정수 N, C, S가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ C ≤ 999, 0 ≤ S ≤ C다.
다음 N개 줄의 i번째 줄에 정수 A_i와 D_i가 공백으로 구분되어 주어진다. 0 ≤ A_i ≤ 999, 0 ≤ D_i ≤ 999다. 전력 유입과 요청은 입력에 적힌 구간 순서대로 발생한다.

출력

차량에 실제로 공급한 전력의 총합과 모든 구간이 끝난 직후의 저장량을 공백으로 구분하여 한 줄에 출력한다.

4 10 3
8 4
0 9
7 2
9 3

15 7

3 5 0
0 4
9 0
0 8

5 0

1 1 1
0 0

0 1

출처: Devin.KR 자체 제작