체류 기간에 맞는 왕복 항공권

문제

여행 준비 프로그램이 한 출발지와 한 목적지 사이의 왕복 항공권을 추천하려고 한다. 프로그램에는 목적지로 가는 편도 항공권 N개와 출발지로 돌아오는 편도 항공권 M개가 등록되어 있다. 가는 항공권과 돌아오는 항공권을 정확히 하나씩 골라 왕복 일정 하나를 만든다. 각 항공권에는 운항 날짜, 가격, 항공사 번호가 기록되어 있다. 날짜는 같은 해의 첫날을 1로 하는 정수로 표현한다. 가는 항공권의 운항 날짜가 D이고 돌아오는 항공권의 운항 날짜가 E라면, 이 일정의 체류 기간은 E−D일이다. 사용자가 지정한 최소 체류 기간 L과 최대 체류 기간 U에 대하여 L ≤ E−D ≤ U를 만족하는 일정만 선택할 수 있다. 다른 시간 정보는 고려하지 않으며, 날짜와 체류 기간 조건을 만족하면 이동이 가능한 것으로 본다. 왕복 일정의 기본 가격은 선택한 두 항공권 가격의 합이다. 두 항공권의 항공사 번호가 같으면 추가 비용이 없고, 다르면 연결 관리 비용 F를 정확히 한 번 더한다. 이렇게 계산한 값을 일정의 총가격이라고 한다. 총가격이 사용자의 예산 B 이하인 일정만 추천할 수 있다. 할인이나 다른 비용은 없으며, 항공사 번호가 다르다는 이유만으로 일정을 제외하지는 않는다. 추천 가능한 일정 중 총가격이 가장 작은 일정을 선택한다. 총가격이 같으면 체류 기간이 짧은 일정을 선택한다. 체류 기간도 같으면 가는 항공권의 입력 번호가 작은 일정을 선택하고, 그 번호도 같으면 돌아오는 항공권의 입력 번호가 작은 일정을 선택한다. 두 목록의 입력 번호는 각각 1부터 독립적으로 매긴다. 날짜, 가격, 항공사가 모두 같은 항공권이 여러 개 주어질 수도 있으며, 이때도 입력 번호가 다르면 별개의 항공권이다. 선택한 항공권의 번호와 총가격을 구하고, 추천 가능한 일정이 하나도 없으면 그 사실을 출력하는 프로그램을 작성한다.

입력

첫째 줄에 N, M, L, U, F, B가 공백으로 구분되어 주어진다. 다음 N개의 줄에는 가는 항공권의 날짜 Dᵢ, 가격 Pᵢ, 항공사 번호 Aᵢ가 주어진다. 이어지는 M개의 줄에는 돌아오는 항공권의 날짜 Eⱼ, 가격 Qⱼ, 항공사 번호 Cⱼ가 주어진다. 각 목록의 항공권 번호는 입력 순서대로 1부터 시작한다.
1 ≤ N, M ≤ 400, 1 ≤ L ≤ U ≤ 364, 0 ≤ F ≤ 1,000,000, 0 ≤ B ≤ 3,000,000이다. 모든 항공권의 날짜는 1 이상 365 이하, 가격은 1 이상 1,000,000 이하, 항공사 번호는 1 이상 20 이하이다. 입력에 등장하는 모든 수는 정수이다.

출력

추천 가능한 일정이 있으면 선택한 가는 항공권 번호, 돌아오는 항공권 번호, 총가격을 한 줄에 공백으로 구분하여 출력한다. 추천 가능한 일정이 없으면 -1만 출력한다.

3 3 2 5 30 250
2 100 1
4 70 2
7 60 1
6 90 1
8 80 2
10 70 1

3 3 130

2 2 1 4 0 100
1 40 1
2 40 2
4 60 2
3 60 1

2 2 100

1 1 2 3 20 100
5 40 1
6 30 2

-1

출처: Devin.KR 자체 제작