카페의 두 잔 시음판

문제

작은 카페가 손님에게 두 가지 음료를 비교해 마실 수 있는 시음판을 제공한다. 오늘 판매하는 음료에는 메뉴판에 적힌 순서대로 1번부터 N번까지 번호가 붙어 있다. 각 음료의 한 잔 가격은 양의 정수이며, 서로 다른 음료의 가격이 같을 수도 있다. 손님은 예산 B 안에서 시음판 하나를 주문하려고 한다. 시음판에는 반드시 서로 다른 메뉴 번호의 음료를 한 잔씩, 정확히 두 잔 담아야 한다. 같은 번호의 음료를 두 잔 고를 수 없으며, 가격이 같더라도 번호가 다르면 함께 고를 수 있다. 시음판의 가격은 고른 두 음료의 가격을 더한 값이다. 할인이나 추가 요금은 없고, 가격의 합이 B와 정확히 같아도 주문할 수 있다. 음료의 재고는 충분하므로 재고 때문에 선택이 제한되지는 않는다. 손님은 주문할 수 있는 시음판 중 가격이 가장 높은 것을 고른다. 가격이 가장 높은 시음판이 여러 개라면, 각 시음판의 두 메뉴 번호를 작은 번호 a와 큰 번호 b로 정리한다. 그다음 a가 가장 작은 시음판을 고르고, a까지 같으면 b가 가장 작은 시음판을 고른다. 이 규칙은 음료의 가격이나 이름이 아닌 메뉴 번호에 적용한다. 따라서 같은 가격의 음료가 여러 개 있어도 최종 선택은 하나로 정해진다. 입력으로 메뉴판 전체와 손님의 예산이 주어진다. 위 규칙에 따라 선택한 두 메뉴 번호와 시음판의 가격을 구하는 프로그램을 작성한다. 정확히 두 잔을 담으면서 예산을 지킬 수 있는 조합이 하나도 없으면 주문 불가를 뜻하는 -1을 출력한다. 메뉴가 하나뿐인 경우에도 두 잔을 구성할 수 없으므로 주문할 수 없다.

입력

첫째 줄에 정수 N과 B가 주어진다. 1≤N≤1,000, 1≤B≤2,000,000이다.
둘째 줄에 1번부터 N번까지의 음료 가격 P_1, …, P_N이 공백으로 구분되어 주어진다. 모든 가격은 정수이며 1≤P_i≤1,000,000이다.

출력

주문할 수 있으면 선택한 메뉴 번호 a, b와 가격의 합을 공백으로 구분하여 한 줄에 출력한다. 이때 a<b이다. 주문할 수 없으면 -1만 출력한다.

5 12
5 7 5 8 4

1 2 12

3 5
3 4 6

-1

4 9
4 4 5 5

1 3 9

출처: Devin.KR 자체 제작