급식 반찬 두 가지

문제

한 학교의 급식 담당자는 특별 급식에 제공할 반찬을 고르고 있다. 후보 반찬은 N가지이며 1번부터 N번까지 번호가 붙어 있다. 각 반찬에는 학생 한 명에게 제공할 때 필요한 재료비와 단백질 점수가 정해져 있다. 단백질 점수는 이 학교가 사용하는 정수 지표이며, 두 반찬을 함께 제공할 때의 점수는 두 반찬 점수의 합으로 계산한다. 이번 특별 급식에는 서로 다른 후보 반찬을 정확히 두 가지 제공해야 한다. 같은 반찬을 두 번 선택할 수 없고, 반찬을 하나만 선택하는 것도 허용되지 않는다. 다른 번호의 반찬이라면 재료비와 단백질 점수가 모두 같더라도 서로 다른 후보로 취급한다. 선택한 두 반찬의 학생 한 명당 재료비 합은 정해진 예산 B원 이하여야 한다. 합이 정확히 B원인 조합도 선택할 수 있다. 담당자는 예산을 지키는 조합 중 단백질 점수의 합이 가장 큰 조합을 선택한다. 그 합이 같은 조합이 여러 개라면 재료비 합이 가장 작은 조합을 선택한다. 단백질 점수 합과 재료비 합이 모두 같다면 각 조합의 두 반찬 번호를 작은 것부터 적은 뒤, 첫 번째 번호가 더 작은 조합을 선택한다. 첫 번째 번호까지 같으면 두 번째 번호가 더 작은 조합을 선택한다. 예산과 각 후보의 정보가 주어질 때 최종적으로 선택할 두 반찬의 번호를 구한다. 반찬의 제공 순서는 선택 결과에 영향을 주지 않으므로 출력할 때는 작은 번호를 먼저 적는다. 모든 반찬의 재료비는 양수이고 단백질 점수는 0일 수도 있다. 예산 안에서 서로 다른 두 반찬을 고를 수 없다면 특별 급식의 반찬 구성을 확정할 수 없으므로 -1을 출력한다. 입력된 후보를 모두 고려해야 하며 번호가 연속한 반찬만 고를 필요는 없다.

입력

첫째 줄에 정수 N과 B가 공백으로 주어진다.
다음 N개 줄 중 i번째 줄에 i번 반찬의 재료비 C_i와 단백질 점수 P_i가 공백으로 주어진다.
2 ≤ N ≤ 300
1 ≤ B ≤ 20,000
1 ≤ C_i ≤ 10,000
0 ≤ P_i ≤ 100
입력에 주어지는 모든 수는 정수다.

출력

선택할 두 반찬의 번호를 작은 번호부터 공백으로 구분하여 한 줄에 출력한다. 예산을 지키는 조합이 없으면 -1을 출력한다.

5 12
5 7
7 8
4 8
6 6
8 8

2 3

4 10
5 6
5 6
5 6
5 6

1 2

3 5
3 100
4 0
6 20

-1

출처: Devin.KR 자체 제작