카페의 세 가지 시음 메뉴

문제

작은 카페에서 새로운 시음 행사를 준비한다. 행사에 사용할 수 있는 음료 후보는 N개이며, 입력에 주어진 순서대로 1번부터 N번까지 번호가 붙어 있다. 각 후보에는 한 잔을 준비하는 데 드는 비용과 맛의 진하기 점수가 정해져 있다. 비용과 점수는 모두 양의 정수다. 이름이나 재료가 비슷한 후보도 번호가 다르면 서로 다른 후보로 취급한다. 같은 후보를 여러 번 골라 수량을 늘리는 방식은 허용하지 않는다. 카페는 서로 다른 후보를 정확히 세 개 골라 하나의 시음 메뉴를 만들려고 한다. 세 후보의 준비 비용을 더한 값은 행사 예산 B 이하여야 한다. 예산과 정확히 같은 비용을 사용하는 것은 허용되며, 남은 예산을 반드시 모두 사용할 필요는 없다. 후보를 두 개 이하로 고르거나 네 개 이상 고르는 것은 허용하지 않는다. 세 후보를 고르는 순서는 메뉴에 영향을 주지 않으므로, 같은 세 후보를 다른 순서로 나열한 것은 같은 메뉴다. 행사 담당자는 시음 메뉴의 전체 진하기를 목표값 T에 가깝게 맞추고 싶다. 전체 진하기는 선택한 세 후보의 진하기 점수를 단순히 더한 값이다. 목표값보다 진해지는 메뉴와 연해지는 메뉴를 모두 허용한다. 메뉴의 차이는 전체 진하기와 T의 차이에 절댓값을 취한 값으로 정의한다. 예산을 지키는 메뉴 중 이 차이가 가장 작은 메뉴를 선택한다. 차이가 같을 때는 준비 비용이나 전체 진하기를 추가 기준으로 사용하지 않는다. 차이가 가장 작은 메뉴가 여러 개라면 각 메뉴의 후보 번호를 오름차순으로 나열한 세 수를 비교한다. 첫 번째 수가 작은 메뉴를 우선하고, 첫 번째 수가 같으면 두 번째 수가 작은 메뉴를 우선한다. 두 번째 수도 같으면 세 번째 수가 작은 메뉴를 우선한다. 이 규칙으로 선택되는 메뉴는 하나로 결정된다. 선택할 세 후보의 번호를 구한다. 예산을 지키면서 서로 다른 세 후보를 고를 수 없다면 메뉴를 만들 수 없다고 판단한다.

입력

첫째 줄에 정수 N, B, T가 주어진다. (3 ≤ N ≤ 80, 1 ≤ B ≤ 3,000, 1 ≤ T ≤ 3,000)
다음 N개 줄 중 i번째 줄에 i번 후보의 준비 비용 C_i와 진하기 점수 S_i가 주어진다. (1 ≤ C_i, S_i ≤ 1,000)
입력에 등장하는 모든 수는 정수다.

출력

메뉴를 만들 수 있다면 선택한 세 후보의 번호를 오름차순으로 한 줄에 공백으로 구분하여 출력한다. 메뉴를 만들 수 없다면 -1을 출력한다.

4 10 12
3 3
4 5
2 4
6 9

1 2 3

4 3 10
1 2
1 3
1 4
1 5

1 2 4

3 5 10
2 3
2 4
2 5

-1

출처: Devin.KR 자체 제작