회의실의 연속 예약

문제

한 회의실의 운영 담당자가 하루 동안 접수된 예약 요청을 검토한다. 요청에는 접수된 순서대로 1번부터 N번까지 번호가 붙어 있으며, i번 요청의 회의 시간은 A_i분이다. 모든 회의 시간은 양의 정수다. 담당자는 일부 요청을 다른 회의실로 옮기고, 이 회의실에서 진행할 요청들을 하나의 운영 묶음으로 정하려 한다. 운영 묶음은 접수 목록에서 연속한 요청들로만 구성해야 한다. 즉, 시작 번호 L과 끝 번호 R을 골랐다면 L번부터 R번까지의 요청을 빠짐없이 포함해야 한다. 그 사이의 요청을 건너뛰거나 요청의 순서를 바꿀 수 없다. 운영 묶음을 정한 뒤에는 선택된 회의들을 바로 이어서 진행하며, 회의 사이의 준비 시간은 따로 필요하지 않다. 이 회의실을 운영 묶음에 사용할 수 있는 시간은 B분이다. 따라서 선택된 회의 시간의 합이 B 이하일 때에만 해당 묶음을 진행할 수 있다. 합이 정확히 B인 경우도 가능하다. 담당자는 이 조건을 지키면서 가능한 한 많은 예약 요청을 포함하려 한다. 전체 회의 시간이 짧은 묶음보다 요청 개수가 많은 묶음을 우선하며, 포함한 요청 개수가 같다면 시작 번호 L이 더 작은 묶음을 선택한다. 선택할 요청이 하나도 없는 빈 묶음은 후보로 취급하지 않는다. 어떤 요청도 단독으로 진행할 수 없다면 진행 가능한 묶음이 없는 것이다. 선택한 묶음의 요청 개수와 시작 번호, 끝 번호를 구해야 한다. 입력의 번호는 모두 접수 순서를 뜻하며, 회의실의 실제 시각이나 날짜를 추가로 고려하지 않는다.

입력

첫째 줄에 정수 N과 B가 주어진다.
둘째 줄에 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 180,000
1 ≤ B ≤ 1,000,000,000
1 ≤ A_i ≤ 9

출력

선택한 묶음의 요청 개수, 시작 번호 L, 끝 번호 R을 공백으로 구분하여 한 줄에 출력한다. 가능한 묶음이 없다면 0 0 0을 출력한다. 요청 개수가 같은 묶음이 여러 개라면 L이 가장 작은 묶음을 출력한다.

7 8
3 2 4 1 2 5 1

3 2 4

4 2
3 4 3 5

0 0 0

5 20
2 1 3 2 1

5 1 5

출처: Devin.KR 자체 제작