두 편의 상영표

문제

작은 영화관에서 관객이 직접 두 편의 영화를 골라 이어 보는 특별 상영을 준비한다. 영화관에는 후보 영화 N편이 있으며, 각 영화에는 입력된 순서대로 1번부터 N번까지 번호가 붙어 있다. i번 영화의 상영 시간은 A_i분이다. 서로 다른 영화라도 상영 시간이 같을 수 있으며, 이때도 서로 다른 후보로 취급한다. 관객은 반드시 서로 다른 영화 두 편을 선택해야 한다. 같은 영화를 두 번 선택하거나 한 편만 선택하는 것은 허용되지 않는다. 선택한 두 영화 사이에는 정리와 입장을 위해 정확히 B분의 휴식 시간을 둔다. 따라서 i번 영화와 j번 영화를 선택하면 전체 행사 시간은 A_i+A_j+B분이다. 전체 행사 시간은 관객이 이용할 수 있는 T분을 넘을 수 없으며, 정확히 T분이 되는 선택은 허용된다. 영화관은 가능한 선택 중 실제로 영화를 보는 시간의 합 A_i+A_j가 가장 큰 선택을 상영표에 넣으려 한다. 휴식 시간은 실제로 영화를 보는 시간에 포함하지 않는다. 상영 시간이 긴 영화 한 편을 먼저 고르는 식으로 결정하지 않고, 조건을 만족하는 두 영화의 조합 전체를 기준으로 결과를 정한다. 같은 최댓값을 만드는 선택이 여러 개라면 각 선택의 두 영화 번호를 작은 번호와 큰 번호 순서로 적는다. 그런 다음 작은 번호가 더 작은 선택을 우선하고, 작은 번호까지 같다면 큰 번호가 더 작은 선택을 우선한다. 출력할 번호의 순서는 실제 상영 순서를 뜻하지 않으며, 두 영화를 식별하기 위한 순서다. 조건을 만족하는 선택이 있다면 최종 선택의 두 번호와 실제 상영 시간의 합을 구한다. 두 편을 고르는 모든 방법이 제한 시간을 넘는다면 선택할 수 없음을 나타낸다. 영화 교체나 추가 휴식 등 여기에 적히지 않은 시간은 발생하지 않는다.

입력

첫째 줄에 정수 N, B, T가 공백으로 구분되어 주어진다. 2≤N≤600, 0≤B≤100, 1≤T≤2000이다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1≤A_i≤1000이다.

출력

선택할 수 있다면 작은 영화 번호, 큰 영화 번호, 두 영화의 상영 시간 합을 공백으로 구분하여 한 줄에 출력한다. 선택할 수 없다면 -1만 출력한다.

5 10 180
70 95 80 90 80

3 4 170

3 5 40
20 21 30

-1

4 0 100
40 60 40 60

1 2 100

출처: Devin.KR 자체 제작