문제
탐험가 개미 베르나르가 사막을 여행 중에 개미지옥에 빠졌다. 개미지옥의 깊이가 L미터로 매우 깊어 단 시간에 빠져 나오기는 힘들다고 판단한 베르나르는 가지고 있던 N병의 에너지 드링크를 적절히 사용하여 개미지옥을 탈출할 작정이다.
베르나르는 k번째 음료수를 마시면 하루에 Ak 미터를 오른다. 하지만 밤에 쉬는 동안 Bk미터를 다시 미끄러진다.
이 사실을 잘 알고 있는 베르나르는 잠시 절망하였으나 운이 좋게도 개미지옥의 깊이와
개미귀신 고스트가 일자별로 몇 미터씩 쫒아오는지에 대한 정보를 입수하였다.
개미귀신 고스트는 낮에는 쉬고 밤에만 쫒아온다고 한다.
더구나 낮에 쉬는 동안 미끄러지지 않는다고 한다.
이제 약간의 희망을 찾은 베르나르는 주어진 정보를 이용하여 개미지옥을 탈출하려고 한다. 과연 탈출할 수 있을까?
입력
입력은 몇 개의 테스트 케이스로 이루어진다. 케이스의 끝은 0 0 이 입력된다.
첫 행에 에너지 음료의 개수 N과 개미지옥의 깊이 L이 공백으로 구분하여 주어진다. ( 1 <= N <= 100,000), ( 1 <= L <= 1,000,000,000)
다음 행부터 N행에 걸쳐 k번 에너지 음료수의 정보 Ak와 Bk가 공백으로 구분하여 주어진다.
다음 행부터 N행에 걸쳐 일자별 개미귀신 고스트의 쫒아오는 길이 Ck가 주어진다. ( 1 <= Ak, Bk, Ck <= 1,000,000,000)
출력
각 테스트 케이스에 대하여 베르나르가 탈출 할 수 있는 가장 빠른 날이 몇 번째 날인지 그 결과를 행으로 구분하여 출력한다.
탈출하지 못하는 경우 -1을 출력한다.
예제
3 9
6 3
5 2
3 1
2
2
2
5 20
3 2
4 2
6 3
8 4
10 5
4
2
3
4
5
5 20
6 5
7 3
10 3
10 14
4 7
2
5
3
9
2
0 0
2
-1
3
출처
jag2016_6
로그인해야 코드를 작성할 수 있어요.