출고 준비가 끝난 날

문제

한 물류 창고는 여러 날에 걸쳐 도착하는 상자를 검사하며 하나의 출고 주문을 준비한다. 이 주문에는 정상 상자 K개가 필요하다. 준비를 시작하기 전에는 주문에 사용할 수 있는 정상 상자가 0개다. 창고 담당자는 앞으로 N일 동안의 입고 기록을 날짜순으로 정리했다. 각 날짜의 기록에는 그날 도착한 전체 상자 수 A와 검사에서 불량으로 판정된 상자 수 B가 들어 있다. 불량 상자는 주문에 사용할 수 없으므로, 해당 날짜에 새로 확보하는 정상 상자는 A-B개다. 정상 상자는 매일 검사를 마친 뒤 준비 구역에 모두 보관한다. 준비 구역의 상자는 기록된 기간 동안 다른 주문에 사용하거나 밖으로 내보내지 않는다. 따라서 어떤 날의 검사가 끝난 뒤 준비 구역에 있는 상자 수는 첫날부터 그날까지 확보한 정상 상자 수의 합이다. 담당자는 하루의 검사를 모두 마쳤을 때만 주문의 준비 상태를 확인한다. 그때까지 확보한 정상 상자 수가 K개 이상이면 주문 준비가 끝난 것으로 본다. 필요한 수량을 정확히 맞출 필요는 없으며, K개보다 많이 확보한 경우에도 준비가 끝난다. 하루 중 상자가 도착한 순서나 검사를 통과한 순서는 주어지지 않으며 계산할 필요도 없다. 창고 기록은 준비가 끝난 뒤에도 N번째 날까지 계속 작성된다. 따라서 주문 준비가 일찍 끝났더라도 이후 날짜에 확보한 정상 상자를 마지막 합계에 포함해야 한다. 그날 도착한 상자가 없거나 도착한 상자가 모두 불량이면 정상 상자 수는 늘어나지 않는다. 이런 날짜도 날짜 번호에 포함한다. 주문 준비가 처음 끝난 날짜 번호와 N일 동안 확보한 정상 상자의 총수를 구하는 프로그램을 작성한다. 날짜 번호는 첫날이 1이고 마지막 날이 N이다. 여러 날에 준비 완료 조건을 만족하더라도 가장 이른 날짜 하나를 사용한다. N번째 날까지 조건을 만족한 날이 없다면 준비 완료 날짜는 0으로 표시한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000이다.
다음 N개 줄에는 첫날부터 날짜순으로 정수 A와 B가 공백으로 구분되어 주어진다. 각 줄에서 0 ≤ B ≤ A ≤ 1,000이다. A는 해당 날짜에 도착한 전체 상자 수이고 B는 그중 불량 상자 수다.

출력

준비가 처음 끝난 날짜 번호와 N일 동안 확보한 정상 상자의 총수를 공백으로 구분하여 한 줄에 출력한다. 준비가 끝난 날이 없으면 날짜 번호로 0을 출력한다.

4 10
5 1
7 2
4 1
3 0

3 15

3 7
4 4
0 0
6 1

0 5

3 5
7 2
2 2
4 0

1 9

출처: Devin.KR 자체 제작