임시 보관대의 하루

문제

물류 창고에는 출고를 기다리는 상자를 올려 두는 임시 보관대가 있다. 보관대에는 상자를 최대 C개까지 놓을 수 있으며, 작업을 시작할 때 보관대는 비어 있다. 모든 상자는 같은 크기이고, 보관대의 남은 공간은 상자 개수만으로 계산한다. 창고는 하루 동안 N차례 작업을 진행한다. 각 작업에는 도착 상자 수 A와 출고 요청 상자 수 B가 정해져 있다. 작업자는 먼저 도착한 상자를 보관대에 올린다. 빈자리가 충분하면 도착한 상자를 모두 올린다. 빈자리가 부족하면 빈자리 수만큼만 올리고, 나머지는 별도 창고로 보낸다. 별도 창고로 보낸 상자는 이후 작업에서 다시 돌아오지 않으며, 임시 보관대의 상자 수에도 포함하지 않는다. 도착 상자 처리가 끝나면 같은 작업의 출고 요청을 처리한다. 보관대에 상자가 B개 이상 있으면 정확히 B개를 꺼낸다. B개보다 적게 있으면 보관대에 있는 상자를 모두 꺼낸다. 이때 채우지 못한 출고 요청은 취소되며, 다음 작업으로 넘기지 않는다. 따라서 이번 작업에서 막 도착해 보관대에 올라간 상자도 곧바로 출고할 수 있다. 작업은 입력에 주어진 순서대로 진행한다. 각 작업이 끝난 뒤 남은 상자는 다음 작업이 시작될 때까지 그대로 보관대에 남는다. 도착 상자 수나 출고 요청 상자 수가 0인 작업도 같은 규칙으로 처리한다. 특히 출고로 빈자리가 생기더라도, 그 작업에서 이미 별도 창고로 보낸 상자를 다시 가져와 올리지는 않는다. 모든 작업을 마친 뒤, 하루 동안 별도 창고로 보낸 상자의 총개수와 임시 보관대에 남은 상자 수를 구하는 프로그램을 작성한다. 별도 창고로 보낸 상자가 한 개도 없다면 그 총개수는 0이다.

입력

첫째 줄에 작업 횟수 N과 보관대의 최대 상자 수 C가 공백으로 구분되어 주어진다. N과 C는 각각 1 이상 1,000 이하의 정수이다.
다음 N개 줄에는 각 작업의 도착 상자 수 A와 출고 요청 상자 수 B가 작업 순서대로 주어진다. A와 B는 각각 0 이상 1,000 이하의 정수이다.

출력

별도 창고로 보낸 상자의 총개수와 모든 작업이 끝난 뒤 보관대에 남은 상자 수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다.

4 8
6 2
7 3
1 9
10 4

5 4

3 5
0 4
5 0
0 5

0 0

1 1
1000 0

999 1

출처: Devin.KR 자체 제작