연속 예약 묶음

문제

한 병원은 다음 날 접수된 예약을 접수 순서대로 정리하고 있다. 예약에는 1번부터 N번까지 번호가 붙어 있으며, i번 예약에 필요한 진료 시간은 A_i분이다. 이 시간에는 해당 환자의 진료와 다음 환자를 맞기 위한 정리 시간이 모두 포함되어 있다. 모든 진료 시간은 양의 정수이며, 예약 순서를 바꾸거나 하나의 예약을 여러 구간으로 나누어 처리할 수 없다. 병원은 별도로 확보한 B분짜리 진료 시간에 예약 일부를 옮기려고 한다. 접수 안내가 복잡해지는 것을 막기 위해 옮기는 예약은 원래 목록에서 번호가 연속해야 한다. 따라서 예약을 하나 이상 옮긴다면 어떤 두 번호 L과 R을 정하여 L번부터 R번까지의 예약을 빠짐없이 옮겨야 한다. 이때 1 ≤ L ≤ R ≤ N이며, 선택한 예약의 진료 시간 합은 B 이하여야 한다. 합이 정확히 B인 경우도 허용된다. 병원이 가장 중요하게 생각하는 것은 옮길 수 있는 예약의 개수다. 조건을 만족하는 구간 가운데 예약 개수가 가장 많은 구간을 선택한다. 그러한 구간이 여러 개라면 시작 번호 L이 가장 작은 구간을 선택한다. 예약 개수와 시작 번호가 정해지면 끝 번호 R도 하나로 정해지므로 추가 동점 규칙은 없다. 남는 진료 시간의 크기는 선택 기준에 포함하지 않는다. 선택한 구간의 예약 개수, 시작 번호, 끝 번호를 출력해야 한다. 단 하나의 예약도 B분 안에 처리할 수 없다면 예약을 옮기지 않으며 세 값으로 모두 0을 출력한다. 입력에 주어진 목록 전체가 선택되는 경우도 허용되며, 첫 예약이나 마지막 예약을 포함하는 구간에도 별도의 제한은 없다.

입력

첫째 줄에 정수 N과 B가 공백으로 주어진다.
둘째 줄에 정수 A_1, A_2, ..., A_N이 공백으로 주어진다.
1 ≤ N ≤ 80,000
1 ≤ B ≤ 1,000,000,000
1 ≤ A_i ≤ 999
입력에 주어지는 모든 수는 정수다.

출력

선택한 구간의 예약 개수, 시작 번호 L, 끝 번호 R을 공백으로 구분하여 한 줄에 출력한다. 선택할 수 있는 예약이 없으면 0 0 0을 출력한다.

7 10
4 2 3 6 1 2 5

3 1 3

4 3
5 4 8 6

0 0 0

5 8
2 1 1 2 2

5 1 5

출처: Devin.KR 자체 제작