배송 띠의 연속 상품

문제

온라인 쇼핑몰의 포장 담당자는 주문 상품을 배송 띠 위에 일렬로 놓았다. 상품은 띠에 놓인 순서대로 1번부터 N번까지 번호가 붙어 있다. i번 상품의 가격은 A_i원이다. 모든 가격은 양의 정수이며, 같은 가격의 상품도 서로 다른 상품으로 취급한다. 담당자는 이 순서를 바꾸거나 중간 상품을 건너뛰지 않고, 연속해서 놓인 상품 일부를 하나의 행사 묶음으로 만들려고 한다. 행사 묶음의 가격 합은 정해진 예산 B원 이하여야 한다. 예산을 정확히 모두 사용할 필요는 없다. 묶음의 시작 번호가 L이고 끝 번호가 R이라면 L번부터 R번까지의 모든 상품이 포함되며, 상품 수는 R-L+1개다. 가격 합이 예산 이하인 묶음 중 상품 수가 가장 많은 것을 선택한다. 상품 수가 같은 후보가 여러 개라면 시작 번호가 가장 작은 후보를 선택한다. 시작 번호와 상품 수가 정해지면 끝 번호도 하나로 정해진다. 배송 띠의 양 끝은 이어져 있지 않다. 따라서 마지막 상품 다음에 첫 번째 상품을 붙여서 묶을 수는 없다. 선택한 구간 밖의 상품 가격이나 다른 묶음을 만들 수 있는지는 이번 선택에 영향을 주지 않는다. 또한 가격이 같은 상품이 이어져 있더라도 각 번호를 하나씩 세어야 한다. 예산보다 비싼 상품 하나를 다른 상품의 할인으로 상쇄하는 규칙도 없다. 행사 묶음은 적어도 하나의 상품을 포함해야 한다. 모든 상품이 예산보다 비싸면 만들 수 있는 묶음이 없다. 이때는 상품 수, 시작 번호, 끝 번호를 모두 0으로 출력한다. 그 외에는 선택된 묶음의 상품 수와 시작 번호, 끝 번호를 순서대로 출력한다. 가격 합 자체는 출력하지 않는다.

입력

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

출력

선택한 묶음의 상품 수, 시작 번호, 끝 번호를 공백으로 구분하여 한 줄에 출력한다. 가능한 묶음이 없으면 0 0 0을 출력한다.

7 10
4 2 3 6 1 2 7

3 1 3

4 2
3 5 3 8

0 0 0

5 8
2 2 2 2 2

4 1 4

출처: Devin.KR 자체 제작