마지막 승객까지 세는 버스

문제

한 마을의 버스는 정류장 N개를 번호가 작은 순서대로 한 번씩 방문한다. 정류장 번호는 1번부터 N번까지이며, 버스가 1번 정류장에 도착하기 전에는 승객이 한 명도 없다. 이 버스에는 운전자를 제외하고 최대 C명의 승객이 탈 수 있다. 노선 담당자는 정류장별 기록을 이용하여 운행 중 버스를 타지 못한 사람의 수를 조사하려 한다. 각 정류장의 기록에는 내린 승객 수 A와 새로 타려고 기다린 사람 수 B가 적혀 있다. 버스가 정류장에 도착하면 먼저 기록에 적힌 A명이 모두 내린다. 그다음 기다리던 B명이 빈자리가 있는 만큼 버스에 탄다. 빈자리가 B개 이상이면 기다리던 사람이 모두 타고, 빈자리가 B개보다 적으면 빈자리 수만큼만 탄다. 타지 못한 사람은 그 정류장에서 기다림을 끝내며, 이후 정류장의 기록에 다시 포함되지 않는다. 승객이 타고 내리는 동안 버스의 정원은 변하지 않는다. 모든 기록은 실제로 가능한 기록이다. 즉, 각 정류장에서 내리는 승객 수는 그 정류장에 도착했을 때 버스 안에 있는 승객 수를 넘지 않는다. 앞선 정류장에서 누가 탔는지는 구분할 필요가 없으며, 정류장을 떠날 때 버스 안에 남은 사람 수만 다음 정류장으로 이어진다. 마지막 정류장에서도 같은 규칙으로 승객이 타고 내린다. 마지막 정류장이라는 이유로 남아 있는 승객이 자동으로 내리지는 않는다. 전체 노선에서 버스를 타지 못한 사람 수의 합과, 한 정류장에서 타지 못한 사람 수가 가장 많았던 정류장 번호를 구한다. 가장 많은 수를 기록한 정류장이 여러 곳이면 번호가 가장 작은 정류장을 고른다. 모든 정류장에서 기다리던 사람이 전부 탔다면 정류장 번호 대신 0을 사용한다. 또한 마지막 정류장을 떠난 직후 버스 안에 있는 승객 수도 함께 구한다.

입력

첫째 줄에 정류장 수 N과 버스 정원 C가 공백으로 구분되어 주어진다. N과 C는 정수이며 1 ≤ N ≤ 90,000, 1 ≤ C ≤ 1,000이다.
다음 N개 줄 중 i번째 줄에 i번 정류장에서 내린 승객 수 A_i와 새로 타려고 기다린 사람 수 B_i가 공백으로 구분되어 주어진다. A_i와 B_i는 정수이며 0 ≤ A_i, B_i ≤ 9이다.
각 A_i는 i번 정류장에 도착한 직후 버스 안에 있는 승객 수 이하임이 보장된다.

출력

첫째 줄에 전체 노선에서 타지 못한 사람 수의 합, 타지 못한 사람 수가 가장 많았던 정류장 번호, 마지막 정류장을 떠난 직후의 승객 수를 순서대로 공백으로 구분하여 출력한다. 최댓값이 같은 정류장이 여러 곳이면 가장 작은 번호를 출력한다. 타지 못한 사람이 한 명도 없으면 정류장 번호로 0을 출력한다.

5 4
0 3
1 5
2 1
0 4
3 2

6 2 3

4 6
0 4
2 1
3 0
0 2

0 0 2

1 1
0 9

8 1 1

출처: Devin.KR 자체 제작