배달 알림을 묶는 구간

문제

한 배달 앱은 가게에 도착한 주문을 접수 순서대로 기록한다. 각 주문에는 가게 화면에 표시할 상세 알림이 있으며, 주문마다 상세 알림이 차지하는 용량이 정해져 있다. 앱 개발자는 화면을 잠시 확인하는 직원이 한 번에 살펴볼 주문 묶음을 만들려고 한다. 주문 묶음에는 접수 기록에서 연속한 주문들만 넣을 수 있다. 접수 기록에는 주문이 1번부터 N번까지 차례대로 놓여 있다. 주문 묶음을 만들려면 시작 번호 L과 끝 번호 R을 정하고, L번부터 R번까지의 모든 주문을 포함해야 한다. 여기서 1 ≤ L ≤ R ≤ N이다. 구간 중간에 있는 주문을 빼거나, 서로 떨어진 여러 구간을 합치는 일은 허용되지 않는다. 선택한 주문의 순서를 바꾸는 일도 없다. 직원이 사용하는 화면은 상세 알림의 총용량이 B 이하인 묶음만 한 번에 표시할 수 있다. 묶음의 총용량은 포함된 주문들의 알림 용량을 모두 더한 값이다. 총용량이 B와 정확히 같아도 표시할 수 있다. 알림을 압축하거나 일부 내용만 표시하는 기능은 없으므로, 주문 하나를 포함할 때는 그 주문의 용량 전체를 더해야 한다. 개발자는 이 조건을 지키면서 한 번에 표시할 수 있는 주문 수를 최대한 크게 하려 한다. 주문 금액이나 배달 거리는 고려하지 않고, 묶음에 포함된 주문 개수만 비교한다. 같은 최대 개수를 가지는 구간이 여러 개라면 어느 구간을 선택하는지는 중요하지 않다. 시작 번호와 끝 번호도 출력할 필요가 없다. 모든 주문의 알림 용량은 양의 정수다. 어떤 주문의 용량이 B보다 클 수도 있으며, 그런 주문을 포함하는 묶음은 표시할 수 없다. 주문 하나만 포함하는 묶음도 허용된다. 표시할 수 있는 비어 있지 않은 묶음이 하나도 없다면 최대 주문 수를 0으로 정한다. 주어진 접수 기록과 화면의 용량 제한을 이용하여, 한 번에 표시할 수 있는 연속한 주문 수의 최댓값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 주문 수 N과 화면의 용량 제한 B가 공백으로 구분되어 주어진다. N은 1 이상 100,000 이하의 정수이고, B는 0 이상 1,000,000,000 이하의 정수다.
둘째 줄에 접수 순서대로 각 주문의 알림 용량 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 각 A_i는 1 이상 1,000,000 이하의 정수다.

출력

알림 용량의 합이 B 이하인 연속 구간에 포함되는 주문 수의 최댓값을 정수 하나로 출력한다. 조건을 만족하는 비어 있지 않은 구간이 없으면 0을 출력한다.

8 10
4 2 3 6 1 2 4 2

4

4 3
4 7 5 9

0

5 5
1 1 1 1 1

5

출처: Devin.KR 자체 제작