단체 손님의 두 객실

문제

한 호텔이 단체 손님을 위해 같은 층에 있는 빈 객실 목록을 정리했다. 목록에는 N개의 객실이 있으며, 객실 번호는 입력 순서대로 1번부터 N번까지다. 각 객실에는 투숙할 수 있는 최대 인원과 하룻밤 이용 요금이 정해져 있다. 이번 예약은 모든 손님이 같은 날 하룻밤을 머무르는 예약이므로, 객실을 여러 날 나누어 이용하는 방법은 고려하지 않는다. 단체의 인원은 P명이고 객실 요금으로 사용할 수 있는 예산은 B다. 예약 담당자는 서로 다른 객실을 정확히 두 개 선택해야 한다. 선택한 두 객실의 최대 인원 합이 P 이상이면 모든 손님을 배정할 수 있다고 본다. 손님은 자유롭게 두 객실에 나눌 수 있고, 선택한 객실 중 하나가 비어 있어도 된다. 두 객실의 정원을 모두 채워야 한다는 조건은 없다. 다만 한 객실만 예약하거나 세 개 이상의 객실을 예약하는 것은 허용하지 않는다. 예약 비용은 선택한 두 객실의 이용 요금을 더한 값이다. 이 비용이 B 이하여야 예산 안에서 예약할 수 있다. 정원 조건과 예산 조건을 모두 만족하는 객실 쌍 가운데 예약 비용이 가장 작은 쌍을 선택하려고 한다. 비용이 같은 쌍이 여러 개라면 각 쌍의 두 번호를 작은 번호부터 적었을 때, 첫 번째 번호가 더 작은 쌍을 선택한다. 첫 번째 번호도 같으면 두 번째 번호가 더 작은 쌍을 선택한다. 객실의 정원이나 요금이 같더라도 번호가 다르면 서로 다른 객실이다. 조건에 맞는 객실 쌍이 있으면 최소 예약 비용과 선택한 두 객실 번호를 출력한다. 조건을 만족하는 쌍이 하나도 없다면 예약할 수 없다는 뜻으로 -1만 출력한다. 예산과 정확히 같은 비용이 드는 쌍도 선택할 수 있다.

입력

첫째 줄에 정수 N, P, B가 공백으로 주어진다. 2 ≤ N ≤ 300, 1 ≤ P ≤ 200, 1 ≤ B ≤ 2,000,000이다.
다음 N개 줄의 i번째 줄에 i번 객실의 최대 인원 C_i와 이용 요금 W_i가 공백으로 주어진다. 모두 정수이며 1 ≤ C_i ≤ 100, 1 ≤ W_i ≤ 1,000,000이다.

출력

조건에 맞는 쌍이 있으면 최소 예약 비용, 작은 객실 번호, 큰 객실 번호를 순서대로 공백으로 구분하여 한 줄에 출력한다. 최소 비용인 쌍이 여러 개면 지문의 동점 처리 규칙을 따른다. 조건에 맞는 쌍이 없으면 -1을 출력한다.

4 7 200
3 70
4 90
5 90
4 100

160 1 2

3 9 100
4 30
4 35
5 80

-1

2 1 12
1 5
1 7

12 1 2

출처: Devin.KR 자체 제작