가장 붐빈 출발 정류장

문제

마을버스 한 대가 차고지를 나와 정해진 노선을 운행한다. 노선에는 N개의 정류장이 있으며, 버스는 1번부터 N번까지 번호 순서대로 각 정류장을 한 번씩 방문한다. 차고지에서 출발할 때 버스에 탄 승객은 없다. 버스에 동시에 탈 수 있는 승객 수는 최대 C명이다. 각 정류장에는 내릴 승객 수와 버스를 기다리는 승객 수가 기록되어 있다. 버스가 i번 정류장에 도착하면 먼저 A_i명이 내린다. 그다음 해당 정류장에서 기다리던 B_i명이 차례로 버스에 타려고 한다. 기다리는 사람이 모두 탈 수 있으면 전원이 탄다. 빈자리가 부족하면 빈자리 수만큼만 타고, 나머지 사람은 정류장에 남는다. 버스는 이 과정이 끝나면 바로 다음 정류장으로 출발한다. 정류장에 남은 사람은 이후 정류장의 기록에 영향을 주지 않는다. 운행 담당자는 버스가 어느 정류장을 출발할 때 가장 붐볐는지 알아보려고 한다. 여기서 출발할 때의 승객 수는 그 정류장에서 내리는 과정과 타는 과정이 모두 끝난 직후 버스 안에 있는 사람 수다. 도착 직전의 승객 수나 기다리는 사람 수를 비교하는 것이 아니다. 마지막인 N번 정류장에서도 같은 규칙으로 승객을 내리고 태운 뒤 출발할 때의 승객 수를 기록한다. 모든 정류장의 출발 기록 중 승객 수의 최댓값과 그 최댓값을 처음 기록한 정류장 번호를 구한다. 같은 최댓값이 여러 번 나오면 번호가 가장 작은 정류장을 선택한다. 모든 정류장을 빈 버스로 출발한 경우에도 기록은 존재하며, 이때 최댓값은 0이고 선택할 정류장은 1번이다. 입력은 실제로 가능한 운행 기록만 주어진다. 따라서 어느 정류장에서도 도착 당시 버스에 타고 있는 사람보다 많은 사람이 내리는 일은 없다.

입력

첫째 줄에 정류장 수 N과 최대 탑승 인원 C가 공백으로 구분되어 주어진다. N과 C는 정수이며 1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000이다.
다음 N개 줄 중 i번째 줄에 정수 A_i와 B_i가 공백으로 구분되어 주어진다. A_i는 i번 정류장에서 내리는 사람 수이고, B_i는 그 정류장에서 기다리는 사람 수다. 0 ≤ A_i ≤ C, 0 ≤ B_i ≤ 1,000이다. A_i는 i번 정류장에 도착했을 때 버스에 타고 있는 승객 수 이하임이 보장된다.

출력

출발할 때의 승객 수의 최댓값과 그 값을 처음 기록한 정류장 번호를 공백으로 구분하여 한 줄에 출력한다.

4 7
0 5
2 6
4 1
0 8

7 2

3 1
0 0
0 0
0 0

0 1

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

4 3

출처: Devin.KR 자체 제작