예약 대기의 합

문제

한 병원은 앞으로 진료받을 사람들의 예약 신청을 날짜별로 처리한다. 운영 담당자는 예약을 처리하지 못하고 다음 날로 넘기는 일이 얼마나 쌓이는지 알아보려고 한다. 이를 위해 N일 동안 매일 업무가 끝났을 때 남은 신청 수를 기록하고, 그 수를 모두 더하기로 했다. 첫날 업무를 시작하기 전에는 처리하지 않은 신청이 B건 있다. 각 날짜의 아침에는 그날의 신규 신청이 모두 접수된다. 따라서 그날 처리할 수 있는 신청은 전날 업무가 끝났을 때 남은 신청과 그날 새로 접수된 신청을 합친 것이다. 병원은 그날 정해진 처리 한도만큼 신청을 처리하되, 처리할 신청이 한도보다 적으면 있는 신청만 모두 처리한다. 처리되지 않은 신청은 사라지지 않고 다음 날로 그대로 넘어간다. 반면 사용하지 못한 처리 한도는 다음 날로 넘길 수 없다. 예를 들어 아침에 처리할 신청이 3건이고 그날의 한도가 8건이면 3건만 처리하며, 남은 5건의 처리 여력은 이후 날짜에 사용할 수 없다. 신규 신청이 없는 날이나 처리 한도가 0인 날도 같은 규칙으로 계산한다. 대기 누적값은 매일 업무 종료 직후 남아 있는 신청 수를 모두 더한 값이다. 같은 신청이 여러 날 동안 남아 있으면 그 신청은 남아 있던 날짜마다 한 번씩 누적값에 포함된다. 처음에 주어진 B건은 첫날 업무 종료 후에도 남아 있는 부분부터 누적값에 포함한다. 아침에 신청이 많았더라도 그날 모두 처리했다면 그날 더하는 값은 0이다. 마지막 날 이후의 처리는 계산하지 않는다. 주어진 일정에 따라 N일을 운영했을 때의 대기 누적값과 마지막 날 업무 종료 직후 남은 신청 수를 구한다. 모든 신청이 처리되어 남은 신청이 없으면 남은 수는 0으로 계산한다.

입력

첫째 줄에 정수 N과 B가 주어진다. 1 ≤ N ≤ 30,000, 0 ≤ B ≤ 1,000이다.
다음 N개 줄의 i번째 줄에 i일의 신규 신청 수 A_i와 처리 한도 C_i가 주어진다. A_i와 C_i는 정수이며 0 ≤ A_i, C_i ≤ 1,000이다.
날짜는 1일부터 N일까지 입력 순서대로 주어진다.

출력

대기 누적값과 마지막 날 업무 종료 직후 남은 신청 수를 공백으로 구분하여 한 줄에 출력한다. 두 값은 모두 정수로 출력한다.

4 2
3 4
4 2
0 1
2 5

6 0

3 1
2 0
0 0
1 1

9 3

1 0
0 1000

0 0

출처: Devin.KR 자체 제작