연결할 항공권 두 장

문제

여행자는 출발 도시에서 환승 도시로 가는 항공권 한 장과 환승 도시에서 도착 도시로 가는 항공권 한 장을 따로 구매하려 한다. 첫 구간 항공권은 N장, 둘째 구간 항공권은 M장이 있으며, 각 구간의 항공권에는 입력에 주어진 순서대로 1번부터 번호가 붙어 있다. 각 항공권에는 출발 시각, 도착 시각, 가격이 적혀 있다. 모든 시각은 여행 계획의 기준 시각부터 지난 분을 나타내므로 날짜가 달라져도 그대로 비교할 수 있다. 첫 구간 항공권의 도착 시각을 a, 둘째 구간 항공권의 출발 시각을 b라고 하자. 두 항공권을 연결하려면 환승 대기 시간 b-a가 L 이상 R 이하여야 한다. L분 또는 R분을 정확히 기다리는 경우도 허용한다. 또한 두 항공권의 가격 합이 여행자의 예산 B 이하여야 한다. 각 항공권의 출발 시각은 도착 시각보다 작지만, 서로 다른 항공권 사이에는 시각 순서나 가격에 관한 별도의 규칙이 없다. 여행자는 조건을 만족하는 조합 중 가격 합이 가장 작은 조합을 선택한다. 가격 합이 같은 조합이 여러 개라면 환승 대기 시간이 가장 짧은 조합을 선택한다. 이것도 같다면 첫 구간 항공권 번호가 작은 조합을 선택하고, 첫 구간 번호까지 같다면 둘째 구간 항공권 번호가 작은 조합을 선택한다. 항공권의 정보가 완전히 같더라도 번호가 다르면 서로 다른 항공권으로 취급한다. 두 구간에서 각각 정확히 한 장을 골라야 하며, 한 구간의 항공권만 구매하는 선택은 허용하지 않는다. 선택한 두 항공권의 번호와 가격 합, 환승 대기 시간을 구하는 프로그램을 작성한다. 조건을 만족하는 조합이 하나도 없다면 항공권을 구매할 수 없다는 결과를 출력한다.

입력

첫째 줄에 정수 N, M, L, R, B가 공백으로 주어진다. 1≤N,M≤600, 0≤L≤R≤1,000,000, 1≤B≤2,000,000이다.
다음 N개 줄에는 첫 구간 항공권의 출발 시각 s, 도착 시각 e, 가격 p가 주어진다. 이어지는 M개 줄에는 둘째 구간 항공권의 정보가 같은 형식으로 주어진다.
모든 항공권에 대해 s,e,p는 정수이며 0≤s<e≤1,000,000, 1≤p≤1,000,000이다. 항공권은 시각이나 가격 순으로 정렬되어 있지 않을 수 있다.

출력

가능한 조합이 있다면 첫 구간 항공권 번호, 둘째 구간 항공권 번호, 가격 합, 환승 대기 시간을 공백으로 구분하여 한 줄에 출력한다. 가능한 조합이 없다면 -1만 출력한다.

2 3 10 40 150
0 50 60
10 70 50
65 100 70
90 130 80
80 110 70

2 3 120 10

1 2 5 10 100
0 30 40
34 60 20
40 80 70

-1

2 2 0 10 100
0 20 30
5 20 30
25 40 40
25 50 40

1 1 70 5

출처: Devin.KR 자체 제작