두 상품으로 채우는 장바구니

문제

온라인 쇼핑몰에서 두 상품을 함께 구매하는 장바구니 행사를 연다. 행사 화면에는 N개의 상품이 나열되어 있으며, 상품에는 화면에 나타난 순서대로 1번부터 N번까지 번호가 붙어 있다. i번 상품의 판매 가격은 P_i원이다. 가격이 같은 상품도 서로 다른 번호를 가진 별개의 상품이다. 이 행사에 참여하려면 화면에 있는 서로 다른 상품을 정확히 두 개 골라야 한다. 같은 상품을 두 번 고를 수 없으며, 상품 하나만 고르는 것도 허용되지 않는다. 두 상품의 가격을 더한 금액이 장바구니의 결제 금액이다. 이 행사에서는 배송비, 할인, 추가 요금이 없으므로 상품 가격의 합이 그대로 결제 금액이 된다. 구매자는 사용할 수 있는 예산 B원을 정해 두었다. 결제 금액이 B원을 초과하는 조합은 구매할 수 없다. 구매자는 예산을 넘지 않는 조합 중 결제 금액이 가장 큰 조합을 고르려고 한다. 예산을 반드시 모두 사용할 필요는 없지만, 사용할 수 있는 금액은 최대한 많이 사용하는 것이 목표다. 결제 금액이 가장 큰 조합이 여러 개라면 각 조합의 두 상품 번호를 작은 번호 i와 큰 번호 j로 정리한다. 먼저 i가 가장 작은 조합을 고르고, i도 같다면 j가 가장 작은 조합을 고른다. 상품의 가격이나 입력에서 발견한 순서는 이 동점 처리 규칙을 바꾸지 않는다. 예를 들어 서로 다른 두 상품의 가격이 같더라도 두 번호를 함께 고를 수 있다. 반면 예산 이하인 상품이 하나 있더라도, 다른 상품을 추가한 모든 조합이 예산을 초과하면 행사에 참여할 수 없다. 주어진 상품 목록에서 규칙에 따라 선택할 두 상품의 번호와 결제 금액을 구한다. 구매할 수 있는 두 상품의 조합이 하나도 없다면 정해진 표시를 출력한다.

입력

첫째 줄에 상품 수 N과 예산 B가 공백으로 구분되어 주어진다.
둘째 줄에 1번부터 N번까지의 상품 가격 P_1, P_2, ..., P_N이 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 2 ≤ N ≤ 500, 1 ≤ B ≤ 2,000,000, 1 ≤ P_i ≤ 1,000,000이다.

출력

구매할 수 있는 조합이 있다면 선택한 상품 번호 i, j와 두 상품의 가격 합을 공백으로 구분하여 한 줄에 출력한다. 이때 i < j여야 하며, 가격 합이 최대인 조합 중 지문의 동점 처리 규칙을 따르는 조합을 출력한다. 구매할 수 있는 조합이 없다면 -1만 출력한다.

5 130
40 90 70 60 90

1 2 130

3 9
5 6 7

-1

2 20
10 10

1 2 20

출처: Devin.KR 자체 제작