도서관의 두 권 전시

문제

작은 도서관은 입구의 전시대에 책 두 권을 함께 소개하려 한다. 전시 후보 책에는 1번부터 N번까지 번호가 붙어 있다. 각 책에는 전시 준비에 필요한 시간과, 그 책을 소개할 때 사용할 수 있는 그림 자료의 수가 정해져 있다. 담당자는 준비 시간 안에 전시를 완성하면서 가능한 한 많은 그림 자료를 보여 주려 한다. 전시에는 서로 다른 책을 정확히 두 권 골라야 한다. 한 권만 고르거나 같은 책을 두 번 고르는 것은 허용되지 않는다. 두 책을 함께 준비하는 데 필요한 시간은 각 책의 준비 시간을 더한 값이다. 두 책의 그림 자료 수 역시 단순히 더한다. 책 사이에 겹치는 자료는 없으며, 함께 선택했을 때 추가 시간이 들거나 시간이 줄어드는 일도 없다. 담당자에게 주어진 전체 준비 시간은 T다. 두 책의 준비 시간 합이 T 이하일 때만 그 조합을 선택할 수 있다. 합이 정확히 T인 조합도 선택할 수 있다. 선택 가능한 조합 중 그림 자료 수의 합이 가장 큰 조합을 찾는다. 준비 시간을 더 적게 사용했다는 이유만으로 우선하는 규칙은 없다. 그림 자료 수의 합이 가장 큰 조합이 여러 개라면 각 조합의 책 번호를 작은 번호 i, 큰 번호 j 순서로 놓고 비교한다. 먼저 i가 더 작은 조합을 고르며, i도 같으면 j가 더 작은 조합을 고른다. 입력에서 준비 시간이나 그림 자료 수가 같은 책도 책 번호가 다르면 서로 다른 책이다. 최종적으로 선택한 두 책의 번호와 그림 자료 수의 합을 출력한다. 준비 시간 조건을 만족하는 두 권의 조합이 하나도 없다면, 전시 구성이 불가능하다는 결과를 출력한다.

입력

첫째 줄에 정수 N과 T가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 100, 1 ≤ T ≤ 2,000이다.
다음 N개 줄 중 k번째 줄에는 k번 책의 준비 시간 t_k와 그림 자료 수 p_k가 공백으로 구분되어 주어진다. t_k와 p_k는 정수이며, 1 ≤ t_k ≤ 1,000, 0 ≤ p_k ≤ 1,000이다.

출력

선택 가능한 조합이 있으면 작은 책 번호 i, 큰 책 번호 j, 두 책의 그림 자료 수의 합을 공백으로 구분하여 한 줄에 출력한다. 동점이면 지문의 책 번호 비교 규칙을 따른다. 선택 가능한 조합이 없으면 -1만 출력한다.

4 9
4 8
5 7
3 10
6 9

3 4 19

4 5
2 5
3 5
1 5
2 5

1 2 10

3 3
2 8
2 9
4 20

-1

출처: Devin.KR 자체 제작