학교 급식 시식 식판

문제

한 학교의 급식 담당자가 새 메뉴를 검토하기 위해 시식 식판 하나를 구성하려고 한다. 시식 후보에는 주식 N종과 곁들임 M종이 있다. 주식에는 입력된 순서대로 1번부터 N번까지, 곁들임에는 별도로 1번부터 M번까지 번호가 붙어 있다. 각 메뉴에는 한 접시의 열량과 재료비가 적혀 있다. 시식 식판에는 주식 한 접시와 곁들임 한 접시를 반드시 담는다. 어느 한쪽을 빼거나 같은 종류를 두 접시 담을 수는 없다. 식판의 총열량은 선택한 두 메뉴의 열량을 더한 값이고, 총재료비는 두 메뉴의 재료비를 더한 값이다. 열량이나 재료비가 같은 메뉴가 여러 개 있더라도 번호가 다르면 서로 다른 후보로 취급한다. 담당자는 총열량이 L 이상 U 이하이고 총재료비가 예산 B 이하인 식판만 시식할 수 있다. 열량이 L 또는 U와 같아도 가능하며, 재료비가 예산과 정확히 같아도 가능하다. 정해진 양의 한 접시를 그대로 담아야 하므로 메뉴의 양을 줄여 열량이나 재료비를 조정할 수는 없다. 두 메뉴 사이에 별도의 조합 제한은 없다. 가능한 식판이 여러 개라면 총열량이 가장 큰 식판을 선택한다. 그중 총열량까지 같다면 총재료비가 가장 작은 식판을 선택한다. 총열량과 총재료비가 모두 같으면 주식 번호가 작은 것을 선택하고, 주식 번호도 같으면 곁들임 번호가 작은 것을 선택한다. 이 우선순위는 앞선 기준으로 결정할 수 없을 때에만 다음 기준을 적용한다는 뜻이다. 모든 주식과 곁들임의 정보가 주어질 때 담당자가 선택할 두 메뉴의 번호를 구한다. 출력할 때는 주식 번호를 먼저 쓰고 곁들임 번호를 뒤에 쓴다. 열량 조건과 예산 조건을 동시에 만족하는 식판이 하나도 없다면 두 메뉴 번호 대신 -1 하나를 출력한다.

입력

첫째 줄에 정수 N, M, L, U, B가 공백으로 구분되어 주어진다. 1 ≤ N, M ≤ 100, 1 ≤ L ≤ U ≤ 2,000, 1 ≤ B ≤ 2,000이다.
다음 N개의 줄에 주식의 정보가 번호 순서대로 주어진다. 각 줄에는 열량 c_i와 재료비 p_i가 주어진다.
그다음 M개의 줄에 곁들임의 정보가 번호 순서대로 주어진다. 각 줄에는 열량 d_j와 재료비 q_j가 주어진다.
모든 열량과 재료비는 1 이상 1,000 이하의 정수이다.

출력

선택한 주식 번호와 곁들임 번호를 공백으로 구분하여 한 줄에 출력한다. 가능한 식판이 없으면 -1을 출력한다.

3 2 400 700 600
400 350
450 400
400 300
200 200
250 250

3 2

2 2 10 20 10
5 3
5 3
5 2
5 2

1 1

1 2 500 600 100
300 80
200 30
100 10

-1

출처: Devin.KR 자체 제작