지하철 시험 운행의 승하차

문제

지하철 운영팀은 한 칸으로 이루어진 시험 열차의 승하차 과정을 모의 실행하려 한다. 열차의 정원은 C명이며, 처음에는 아무도 타고 있지 않다. 열차는 1번부터 N번까지의 역을 번호순으로 한 번씩 방문한다. 각 역에는 내리려는 인원 요청과 새로 타려는 대기 인원이 주어진다. 시험 자료의 하차 요청은 실제 승객의 목적지를 추적해서 만든 값이 아니다. 따라서 어떤 역에서는 하차 요청 인원이 현재 열차 안의 승객 수보다 많을 수도 있다. 이 경우에는 현재 타고 있는 승객이 모두 내린다. 즉, 실제 하차 인원은 하차 요청 인원과 도착 당시 승객 수 중 작은 값이다. 요청한 만큼 내릴 승객이 없더라도 오류로 처리하거나 다음 역으로 요청을 넘기지 않는다. 각 역에서는 반드시 하차를 먼저 끝낸 다음 승차를 진행한다. 하차가 끝난 뒤 열차에 남은 빈자리 수를 계산하고, 대기 인원 중 그 수만큼까지 태운다. 빈자리가 대기 인원보다 많으면 대기 인원이 모두 타고, 대기 인원이 빈자리보다 많으면 정원이 찰 때까지만 탄다. 이 과정에서 열차 안의 승객 수는 항상 0 이상 C 이하로 유지된다. 해당 역에서 타지 못한 사람들은 그 역에 남으며 이후 계산에는 다시 등장하지 않는다. 다음 역에 주어지는 대기 인원은 이전 역에서 남은 인원과 무관한 새로운 값이다. 운영팀은 모든 역에서 타지 못한 인원을 합한 값이 필요하다. 같은 사람이 다시 줄을 서는 상황은 없으므로 각 역의 남은 인원을 그대로 더하면 된다. 또한 매 역에서 승하차를 모두 마친 직후의 열차 안 승객 수를 기록한다. 이 기록들 중 가장 큰 승객 수와, 그 값이 처음 나타난 역 번호를 구해야 한다. 도착 직전이나 하차만 끝난 시점의 인원은 이 최댓값의 비교 대상이 아니다. 모든 역의 기록이 0명이면 최댓값은 0명이고 처음 나타난 역은 1번이다. 마지막 역에서도 같은 규칙으로 승하차하며 이후에 추가 하차 처리를 하지 않는다. 시험 운행을 끝까지 실행한 결과를 출력하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 40,000, 1 ≤ C ≤ 99)
다음 N개 줄에 각 역의 하차 요청 인원 A와 대기 인원 B가 공백으로 구분되어 주어진다. 입력의 i번째 인원 정보는 i번 역을 나타낸다.
A와 B는 정수이며 0 ≤ A ≤ 99, 0 ≤ B ≤ 99이다.

출력

첫째 줄에 마지막 역의 승하차를 마친 뒤 열차 안 승객 수와 모든 역에서 타지 못한 인원의 합을 공백으로 구분하여 출력한다. 둘째 줄에 역별 승하차 완료 직후 승객 수의 최댓값과 그 값이 처음 나타난 역 번호를 공백으로 구분하여 출력한다.

4 5
0 7
2 1
9 3
1 6

5 5
5 1

3 4
8 0
0 0
2 0

0 0
0 1

3 6
0 2
1 3
2 4

6 0
6 3

출처: Devin.KR 자체 제작