세 곡 미리 듣기

문제

음악 스트리밍 서비스에서 재생 목록의 일부를 소개하는 미리 듣기 구간을 만들려고 한다. 재생 목록에는 N개의 곡이 있으며, 곡에는 현재 나열된 순서대로 1번부터 N번까지 번호가 붙어 있다. 각 곡의 재생 시간은 초 단위의 양의 정수로 주어진다. 같은 재생 시간을 가진 곡도 서로 다른 곡으로 취급한다. 미리 듣기 구간은 재생 목록에서 연속한 정확히 세 곡으로 구성한다. 시작 곡이 i번이라면 i번, i+1번, i+2번 곡을 이 순서대로 끝까지 재생한다. 곡의 일부만 재생하거나, 중간의 곡을 건너뛰거나, 곡의 순서를 바꿀 수 없다. 마지막 곡 다음에 첫 번째 곡이 이어지는 것도 아니다. 따라서 시작 곡의 번호는 1 이상 N-2 이하여야 한다. 서비스에는 미리 듣기에 사용할 수 있는 시간 B초가 정해져 있다. 세 곡의 재생 시간 합이 B 이하인 구간만 선택할 수 있다. 이 조건을 만족하는 구간 중 재생 시간 합이 가장 큰 구간을 선택한다. 재생 시간 합이 같은 구간이 여러 개라면 시작 곡의 번호가 가장 작은 구간을 선택한다. 곡 사이의 전환에는 시간이 들지 않으므로 세 곡의 재생 시간만 더한다. 선택한 구간의 시작 곡 번호와 재생 시간 합을 구하는 프로그램을 작성한다. 세 곡의 합이 B와 정확히 같아도 선택할 수 있다. 조건을 만족하는 구간이 하나도 없다면 한 곡이나 두 곡으로 대신 구성하지 않고, 미리 듣기 구간을 만들 수 없다고 처리한다.

입력

첫째 줄에 정수 N과 B가 공백으로 구분되어 주어진다. 3 ≤ N ≤ 100,000, 1 ≤ B ≤ 297이다.
둘째 줄에 각 곡의 재생 시간 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 모든 A_i는 정수이며 1 ≤ A_i ≤ 99이다.

출력

조건을 만족하는 구간이 있으면 시작 곡 번호와 세 곡의 재생 시간 합을 공백으로 구분하여 출력한다. 조건을 만족하는 구간이 없으면 -1만 출력한다.

6 16
4 7 3 6 5 2

2 16

5 9
3 3 3 3 3

1 9

3 5
2 2 2

-1

출처: Devin.KR 자체 제작