예약표에서 고른 한 칸

문제

한 병원은 취소된 예약을 다시 받을 때, 그날 선택할 수 있는 예약 칸을 한꺼번에 공개한다. 각 예약 칸에는 시작 시각, 종료 시각, 예약 비용이 적혀 있다. 예약 칸은 입력된 순서대로 1번부터 N번까지 번호가 붙는다. 서로 다른 진료실에서 나온 예약 칸도 함께 공개하므로 시간이 겹치는 칸이 있을 수 있으며, 세 정보가 모두 같은 칸도 서로 다른 번호로 남아 있다. 예약을 신청하려는 사람은 시각 A부터 시각 B까지 병원에 머무를 수 있다. 또한 필요한 진료를 받으려면 예약 칸의 길이가 D분 이상이어야 하고, 예약 비용은 C 이하이어야 한다. 이 사람은 공개된 예약 칸 중 정확히 하나를 선택하려 한다. 여러 칸을 합쳐서 예약할 수는 없다. 예약 칸은 표시된 시작 시각부터 종료 시각까지 통째로 이용해야 한다. 따라서 선택할 칸의 시작 시각은 A 이상이고 종료 시각은 B 이하여야 한다. 필요한 진료가 일찍 끝나더라도 예약 칸의 일부만 이용하는 것으로 조건을 판단하지 않는다. 예약 칸의 길이는 종료 시각에서 시작 시각을 뺀 값이다. 시작 시각이 A와 같거나 종료 시각이 B와 같은 경우도 허용한다. 조건을 만족하는 칸이 여러 개라면 비용이 가장 작은 칸을 선택한다. 비용까지 같다면 시작 시각이 가장 이른 칸을 선택하고, 시작 시각도 같다면 번호가 가장 작은 칸을 선택한다. 종료 시각은 이 우선순위에 영향을 주지 않는다. 모든 시각은 그날 0시부터 지난 분을 나타내는 정수이다. 공개된 예약표를 조사하여 선택할 칸의 번호를 구한다. 조건을 만족하는 칸이 없다면 -1을 출력한다.

입력

첫째 줄에 정수 N, A, B, D, C가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 20,000
0 ≤ A < B ≤ 1,440
1 ≤ D ≤ 1,440
1 ≤ C ≤ 9,999
다음 N개 줄에는 예약 칸의 시작 시각 s, 종료 시각 e, 비용 p가 공백으로 구분되어 주어진다. 이 중 i번째 줄이 i번 예약 칸이다.
0 ≤ s < e ≤ 1,440
1 ≤ p ≤ 9,999
입력으로 주어지는 모든 수는 정수이다. 예약 칸의 시간이 서로 겹치거나 같은 정보가 반복될 수 있다.

출력

선택할 예약 칸의 번호를 정수 하나로 출력한다. 조건을 만족하는 예약 칸이 없다면 -1을 출력한다.

6 480 720 30 500
500 550 400
490 530 300
480 510 300
480 540 300
470 520 200
600 620 100

3

3 600 660 40 200
600 630 100
590 650 150
620 660 201

-1

4 0 1440 1440 9999
0 1440 9999
0 1439 1
1 1440 1
0 1440 9999

1

출처: Devin.KR 자체 제작