환승 없는 노선 고르기

문제

한 마을의 버스 안내소는 출발 정류장에서 목적 정류장까지 환승 없이 갈 수 있는 노선들을 정리하고 있다. 안내소가 조사한 노선은 N개이며, 입력에 등장하는 순서대로 1번부터 N번까지 번호를 붙인다. 서로 다른 노선의 요금과 소요 시간이 모두 같을 수도 있지만, 번호가 다르면 서로 다른 노선으로 취급한다. 각 노선에는 한 사람이 내야 하는 요금 C와 목적 정류장까지 가는 데 걸리는 시간 T가 기록되어 있다. T에는 버스를 기다리는 시간과 버스에 타고 이동하는 시간이 이미 모두 포함되어 있다. 따라서 노선을 비교할 때 별도의 대기 시간이나 이동 시간을 더할 필요가 없다. 모든 노선은 출발 정류장과 목적 정류장을 직접 연결하며, 중간에 다른 노선으로 갈아타는 선택은 허용하지 않는다. 이용자가 이번 이동에 쓸 수 있는 금액은 B이다. 요금이 B 이하인 노선만 이용할 수 있으며, 예산을 전부 써도 된다. 요금이 0인 무료 노선도 있을 수 있다. 안내소는 이용할 수 있는 노선 중 소요 시간이 가장 짧은 노선을 추천한다. 가장 짧은 시간이 같은 노선이 여러 개라면 요금이 더 낮은 노선을 추천한다. 시간과 요금이 모두 같다면 번호가 가장 작은 노선을 추천한다. 노선의 번호 자체에는 요금이나 시간에 관한 정보가 들어 있지 않다. 앞쪽에 적힌 노선이 더 빠르거나 더 저렴하다는 보장도 없다. 주어진 모든 후보와 이용자의 예산을 바탕으로 추천할 노선 번호를 구해야 한다. 예산 안에서 이용할 수 있는 노선이 하나도 없다면 추천할 수 없음을 나타내는 -1을 출력한다.

입력

첫째 줄에 정수 N과 B가 주어진다.
다음 N개 줄의 i번째 줄에 i번 노선의 요금 C_i와 소요 시간 T_i가 정수로 주어진다.
1 ≤ N ≤ 20,000
0 ≤ B ≤ 9,999
0 ≤ C_i ≤ 9,999
1 ≤ T_i ≤ 9,999

출력

규칙에 따라 추천할 노선의 번호를 출력한다. 이용 가능한 노선이 없으면 -1을 출력한다.

5 60
50 35
60 30
40 30
40 30
70 10

3

3 4
5 10
8 2
6 9

-1

2 0
0 8
0 8

1

출처: Devin.KR 자체 제작