빈 시간의 두 운동

문제

한 헬스장에서는 회원이 잠깐 생긴 빈 시간을 활용할 수 있도록 짧은 운동 프로그램을 제공한다. 오늘 이용할 수 있는 프로그램은 N개이며, 안내판에 적힌 순서대로 1번부터 N번까지 번호가 붙어 있다. i번 프로그램을 처음부터 끝까지 수행하는 데 걸리는 시간은 A_i분이다. 각 프로그램의 소요 시간은 준비와 정리 시간을 이미 포함하므로, 두 프로그램을 연달아 수행할 때 별도의 시간은 추가되지 않는다. 회원에게 남은 시간은 T분이다. 회원은 서로 다른 프로그램을 정확히 두 개 골라 각각 한 번씩 수행하려 한다. 선택한 두 프로그램의 소요 시간 합이 T 이하이면 남은 시간 안에 운동을 마칠 수 있다. 시간을 초과하는 조합은 선택할 수 없으며, 프로그램을 중간에 끝내거나 같은 프로그램을 두 번 수행하는 것도 허용되지 않는다. 소요 시간이 같더라도 번호가 다르면 서로 다른 프로그램이다. 회원은 가능한 조합 중 소요 시간의 합이 가장 큰 조합을 원한다. 두 프로그램의 수행 순서는 선택 결과에 영향을 주지 않으므로, 각 조합은 작은 번호 i와 큰 번호 j로 나타낸다. 소요 시간의 합이 같은 최적의 조합이 여러 개이면 i가 가장 작은 조합을 고른다. i까지 같으면 j가 가장 작은 조합을 고른다. 따라서 조건을 만족하는 조합이 하나라도 있다면 선택 결과는 항상 하나로 정해진다. 안내판의 소요 시간과 회원에게 남은 시간이 주어질 때 선택할 두 프로그램의 번호와 소요 시간의 합을 구한다. 정확히 두 프로그램을 골라야 하므로, 한 프로그램만 수행할 수 있는 경우에도 가능한 조합이 없는 것으로 처리한다.

입력

첫째 줄에 정수 N과 T가 공백으로 주어진다. 2 ≤ N ≤ 200, 2 ≤ T ≤ 20,000이다.
둘째 줄에 정수 A_1, A_2, ..., A_N이 공백으로 주어진다. 모든 i에 대해 1 ≤ A_i ≤ 10,000이다.

출력

가능한 조합이 있으면 선택한 번호 i, j와 소요 시간의 합을 한 줄에 공백으로 구분하여 출력한다. 반드시 i < j여야 한다. 가능한 조합이 없으면 -1만 출력한다.

5 15
6 9 7 8 9

1 2 15

3 5
4 4 6

-1

4 12
5 6 6 5

2 3 12

출처: Devin.KR 자체 제작