주차장이 가장 붐빈 점검

문제

주차장 관리인은 영업 중 정해진 순서로 N번 점검하며 주차된 차량 수를 기록한다. 영업을 시작하기 직전 주차장에 있던 차량 수는 S대이다. 각 점검 기록에는 직전 점검 이후 들어온 차량 수와 나간 차량 수가 함께 적혀 있다. 첫 번째 점검 기록은 영업 시작 직전부터 첫 번째 점검까지의 변화를 나타낸다. 관리인은 이 기록을 이용하여 점검 시점 가운데 차량이 가장 많았던 때를 찾으려 한다. 영업 시작 직전의 상태를 0번 점검이라고 부른다. 이후 실제 점검에는 기록이 주어진 순서대로 1번부터 N번까지 번호를 붙인다. i번 점검의 차량 수는 i-1번 점검의 차량 수에 이번 기록의 입차 대수를 더하고 출차 대수를 뺀 값이다. 각 기록의 두 대수는 모두 0 이상 100 이하의 정수이다. 입력은 매번 계산한 차량 수가 0 이상이 되도록 주어진다. 주차장의 수용 대수에 따른 별도 제한은 없다. 비교 대상에는 실제로 수행한 1번부터 N번 점검뿐 아니라 0번 점검도 포함된다. 차량 수의 최댓값이 여러 점검에서 같으면 번호가 가장 작은 점검을 선택한다. 따라서 이후의 차량 수가 시작 직전의 차량 수를 한 번도 넘지 않았다면 선택되는 점검 번호는 0이다. 입차와 출차가 모두 없는 기록도 하나의 점검으로 세며, 그 점검의 차량 수는 직전 점검과 같다. 한 기록 안에서 차량들이 실제로 출입한 순서는 제공되지 않는다. 기록 사이에 잠시 차량이 더 많았을 가능성은 고려하지 않고, 각 점검이 끝난 시점의 차량 수만 비교한다. 입차 대수의 합이나 출차 대수의 합을 따로 최댓값과 비교해서도 안 된다. 기록을 순서대로 반영했을 때의 차량 수를 사용해야 한다. 가장 많은 차량 수와 그 수가 처음 나타난 점검 번호를 공백으로 구분하여 출력한다.

입력

첫째 줄에 점검 수 N과 영업 시작 직전의 차량 수 S가 주어진다. N은 1 이상 1,000 이하의 정수이고 S는 0 이상 100 이하의 정수이다.
다음 N개 줄에는 각 점검의 입차 대수 E와 출차 대수 X가 순서대로 주어진다. E와 X는 각각 0 이상 100 이하의 정수이다. 모든 점검에서 직전 차량 수에 E를 더하고 X를 뺀 결과는 0 이상임이 보장된다.

출력

0번부터 N번까지의 점검 중 가장 많은 차량 수와 그 차량 수가 처음 나타난 점검 번호를 공백으로 구분하여 한 줄에 출력한다.

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

8 4

3 5
0 2
2 0
0 0

5 0

4 0
2 0
0 2
2 0
0 0

2 1

출처: Devin.KR 자체 제작