쉬어 갈 정류장

문제

새로 만든 버스 노선에서 운행 중 잠시 쉬어 갈 정류장을 정하려 한다. 버스는 출발 정류장에서 출발하여 1번 정류장부터 N번 정류장까지 번호 순서대로 이동한다. 출발 정류장에는 번호가 없으며, 쉬어 갈 정류장으로 선택할 수 없다. 각 정류장에는 버스가 잠시 머물 수 있는 대기 공간이 있을 수도 있고 없을 수도 있다. 운행 담당자는 출발한 뒤 누적 이동 시간이 T분 이상이 된 다음에 쉬도록 정했다. 따라서 어떤 정류장을 선택하려면 그 정류장에 도착했을 때의 누적 이동 시간이 T분 이상이어야 하고, 그 정류장에 대기 공간도 있어야 한다. 두 조건을 모두 만족하는 정류장 중 가장 먼저 도착하는 정류장 하나를 선택한다. 정류장은 번호 순서대로 방문하므로 이는 조건을 만족하는 정류장 중 번호가 가장 작은 정류장이다. i번 정류장의 이동 시간 A_i는 바로 앞 정류장에서 i번 정류장까지 걸리는 시간이다. 특히 A_1은 출발 정류장에서 1번 정류장까지 걸리는 시간이다. 출발할 때의 누적 이동 시간은 0분이며, i번 정류장에 도착했을 때의 누적 이동 시간은 A_1부터 A_i까지의 합이다. 승객이 타고 내리는 시간은 계산에 포함하지 않는다. 누적 이동 시간이 정확히 T분인 경우에도 시간 조건을 만족한다. 시간이 충분히 지났더라도 대기 공간이 없는 정류장은 선택할 수 없으며, 그 정류장을 지나도 누적 이동 시간은 초기화되지 않는다. 정류장 사이를 이동하는 도중에는 쉴 수 없다. 마지막인 N번 정류장도 다른 정류장과 같은 규칙으로 선택할 수 있다. 노선의 이동 시간과 대기 공간 정보를 바탕으로 처음 쉬어 갈 정류장의 번호를 구한다. 모든 정류장을 확인해도 두 조건을 만족하는 곳이 없다면 -1을 출력한다.

입력

첫째 줄에 정류장의 수 N과 기준 시간 T가 공백으로 구분되어 주어진다. N과 T는 정수이며 1 ≤ N ≤ 1,000, 1 ≤ T ≤ 1,000,000이다.
다음 N개 줄 중 i번째 줄에 정수 A_i와 B_i가 공백으로 구분되어 주어진다. 1 ≤ A_i ≤ 1,000이다. B_i는 0 또는 1이며, 1이면 i번 정류장에 대기 공간이 있고 0이면 없다는 뜻이다.

출력

처음 쉬어 갈 정류장의 번호를 정수 하나로 출력한다. 조건을 만족하는 정류장이 없으면 -1을 출력한다.

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

4

3 7
2 0
5 1
4 1

2

4 10
3 1
2 1
6 0
1 0

-1

출처: Devin.KR 자체 제작