충전기 목록의 첫 빈자리

문제

한 전기차 충전소는 입구 안내판에 충전기 목록을 보여 준다. 충전기에는 안내판에 표시된 순서대로 1번부터 N번까지 번호가 붙어 있다. 번호는 위치를 구별하기 위한 것으로, 충전기의 성능이 좋은 순서나 빈 시간이 긴 순서를 뜻하지 않는다. 안내판에는 각 충전기를 지금 사용할 수 있는지와 그 충전기가 지원하는 최대 출력이 함께 기록되어 있다. 충전소에 도착한 운전자는 자신의 차량을 충전할 충전기 하나를 고르려 한다. 운전자는 최대 출력이 P 이상인 충전기만 사용한다. 최대 출력이 정확히 P인 충전기도 사용할 수 있다. 또한 이미 다른 차량이 사용 중인 충전기는 출력이 충분하더라도 선택할 수 없다. 충전기의 사용 상태는 0 또는 1로 주어지며, 0은 비어 있음을, 1은 다른 차량이 사용 중임을 뜻한다. 운전자는 안내판의 첫 번째 항목부터 차례대로 읽으며, 비어 있고 최대 출력이 P 이상인 충전기를 처음 발견하면 그 충전기를 선택한다. 조건을 만족하는 충전기가 여러 개라면 번호가 가장 작은 충전기를 선택하는 셈이다. 더 큰 출력을 지원하는 충전기가 뒤에 있더라도 이미 찾은 충전기를 바꾸지 않는다. 이 문제에서 차량과 충전기의 연결 방식은 모두 같으므로 다른 호환 조건은 확인할 필요가 없다. 안내판을 확인하는 동안 각 충전기의 사용 상태와 최대 출력은 변하지 않는다. 운전자가 충전기를 선택한 이후의 충전 과정도 계산하지 않는다. 주어진 목록에서 이 운전자가 선택할 충전기의 번호 하나만 구하면 된다. 목록을 끝까지 살펴보아도 두 조건을 모두 만족하는 충전기가 없다면 선택할 수 없다는 뜻으로 0을 출력한다.

입력

첫째 줄에 충전기 수 N과 필요한 출력 P가 공백으로 구분되어 주어진다. 다음 N개 줄의 i번째 줄에 i번 충전기의 사용 상태 S_i와 최대 출력 W_i가 공백으로 구분되어 주어진다. 모든 입력은 정수이며, 1 ≤ N ≤ 1,000, 1 ≤ P ≤ 350, S_i는 0 또는 1, 1 ≤ W_i ≤ 350이다.

출력

비어 있으면서 최대 출력이 P 이상인 충전기 중 번호가 가장 작은 충전기의 번호를 출력한다. 그러한 충전기가 없다면 0을 출력한다.

5 80
1 150
0 60
0 80
0 200
1 100

3

3 120
0 50
1 200
0 119

0

1 350
0 350

1

출처: Devin.KR 자체 제작