두 장으로 정하는 여행 기간

문제

한 여행자는 출발 도시와 여행 도시를 왕복하는 항공권을 따로 구매하려 한다. 여행 도시로 가는 편도 항공권 후보는 N장이고, 출발 도시로 돌아오는 편도 항공권 후보는 M장이다. 가는 항공권은 입력 순서대로 1번부터 N번까지, 돌아오는 항공권은 별도로 1번부터 M번까지 번호를 붙인다. 여행자는 두 목록에서 각각 정확히 한 장씩 선택해야 한다. 각 항공권에는 이동하는 날짜와 가격이 적혀 있다. 날짜는 같은 기준일에서 센 양의 정수로 나타내며, 모든 항공편은 표시된 날짜 안에 출발하여 도착한다고 가정한다. 가는 항공권의 날짜를 a, 돌아오는 항공권의 날짜를 b라고 할 때 a < b여야 여행이 가능하다. 같은 날짜에 갔다가 돌아오는 조합은 허용하지 않는다. 여행 기간은 두 날짜의 차이인 b - a로 정의하며, 항공편의 구체적인 출발 시각이나 비행시간은 고려하지 않는다. 여행자가 항공권 구매에 사용할 수 있는 예산은 B다. 선택한 두 항공권의 가격 합이 B 이하여야 하며, 다른 비용은 계산하지 않는다. 가격 합이 예산과 정확히 같아도 선택할 수 있다. 모든 후보는 해당 방향의 같은 두 도시를 연결하므로 도시나 공항이 맞는지 추가로 확인할 필요는 없다. 서로 다른 번호의 항공권은 날짜와 가격이 같더라도 별개의 후보로 취급한다. 여행자는 가능한 조합 중 여행 기간이 가장 긴 조합을 고른다. 여행 기간이 같으면 두 항공권의 가격 합이 더 작은 조합을 고른다. 가격 합도 같으면 가는 항공권 번호가 더 작은 조합을 고르고, 그 번호까지 같으면 돌아오는 항공권 번호가 더 작은 조합을 고른다. 이 순서를 모두 적용하면 선택할 조합은 하나로 정해진다. 날짜 조건과 예산 조건을 함께 만족하는 조합이 없을 수도 있다. 두 항공권 목록과 예산이 주어질 때, 여행자가 선택할 항공권 번호와 여행 기간, 가격 합을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, M, B가 공백으로 주어진다. 다음 N개 줄에 가는 항공권의 날짜 a_i와 가격 p_i가 주어진다. 그다음 M개 줄에 돌아오는 항공권의 날짜 b_j와 가격 q_j가 주어진다.
1 ≤ N, M ≤ 300, 1 ≤ B ≤ 2,000,000이다. 모든 날짜는 1 이상 365 이하의 정수이며 모든 가격은 1 이상 1,000,000 이하의 정수다. 각 목록은 날짜나 가격순으로 정렬되어 있지 않을 수 있다.

출력

가능한 조합이 있으면 가는 항공권 번호, 돌아오는 항공권 번호, 여행 기간, 두 항공권의 가격 합을 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 문제에 제시된 순서대로 동점을 처리한다. 가능한 조합이 없으면 -1만 출력한다.

3 3 150
2 70
4 50
1 100
8 80
6 40
3 20

1 1 6 150

2 2 100
5 20
6 30
4 10
5 10

-1

2 2 90
2 40
2 40
7 30
7 30

1 1 5 70

출처: Devin.KR 자체 제작