카페의 시음 세트 선정

문제

작은 카페에서 새 메뉴를 소개하는 시음 행사를 준비하고 있다. 행사 담당자는 음료 한 종류와 구움과자 한 종류를 골라 하나의 시음 세트를 만들려고 한다. 음료와 구움과자는 각각 별도의 목록에 등록되어 있으며, 각 목록에서 위쪽에 있는 메뉴부터 1번, 2번과 같이 번호를 붙인다. 두 목록의 번호는 서로 독립적이므로 음료 1번과 구움과자 1번은 다른 메뉴를 뜻한다. 각 메뉴에는 시음용 한 개를 준비하는 비용이 정해져 있다. 세트 하나의 준비 비용은 선택한 음료의 비용과 선택한 구움과자의 비용을 더한 값이다. 두 메뉴 사이에 할인이나 추가 비용은 없다. 담당자는 정해진 예산 이하의 비용으로 만들 수 있는 세트 중 준비 비용이 가장 큰 세트를 선택하려 한다. 예산과 비용이 정확히 같아도 선택할 수 있다. 같은 준비 비용을 갖는 세트가 여러 개라면 선택 기준을 순서대로 적용한다. 먼저 음료 번호가 가장 작은 세트를 고른다. 음료 번호까지 같다면 구움과자 번호가 가장 작은 세트를 고른다. 서로 다른 번호의 메뉴는 준비 비용이 같더라도 별개의 메뉴로 취급한다. 따라서 비용이 중복된 목록에서도 메뉴 번호를 기준으로 결과를 결정해야 한다. 음료만 고르거나 구움과자만 고르는 것은 세트로 인정하지 않는다. 반드시 각 목록에서 정확히 하나씩 골라야 하며, 어느 조합도 예산을 만족하지 못한다면 세트를 선정할 수 없다. 메뉴 목록의 순서를 바꾸어 번호를 다시 붙이는 일도 하지 않는다. 모든 음료와 구움과자의 조합을 살펴보고, 정해진 기준에 따라 선정할 두 메뉴의 번호와 준비 비용을 구하는 프로그램을 작성한다.

입력

첫째 줄에 음료 수 N, 구움과자 수 M, 예산 B가 공백으로 구분되어 주어진다. 모두 정수이며 1 ≤ N, M ≤ 100, 1 ≤ B ≤ 2,000,000이다.
둘째 줄에 음료 1번부터 N번까지의 준비 비용이 주어진다.
셋째 줄에 구움과자 1번부터 M번까지의 준비 비용이 주어진다.
각 준비 비용은 1 이상 1,000,000 이하의 정수이다.

출력

세트를 선정할 수 있으면 음료 번호, 구움과자 번호, 두 비용의 합을 공백으로 구분하여 한 줄에 출력한다. 선정할 수 없으면 -1을 출력한다.

3 3 12
7 4 7
5 8 3

1 1 12

2 2 5
4 6
3 2

-1

2 3 10
4 4
5 6 6

1 2 10

출처: Devin.KR 자체 제작