서가 한 구간의 점검

문제

도서관의 한 서가에는 왼쪽부터 1번부터 N번까지 번호가 붙은 책이 놓여 있다. 사서는 책마다 표지와 분류표를 점검하는 데 필요한 시간을 미리 기록했다. 책 한 권의 점검 시간은 1분 이상 9분 이하의 정수이며, 점검을 시작한 책은 끝까지 확인해야 한다. 책의 위치를 바꾸거나 일부 점검만 수행할 수는 없다. 오늘 이 서가의 점검에 사용할 수 있는 시간은 T분이다. 사서는 서가에서 연속한 책들을 하나의 작업 구간으로 정하고, 그 구간에 속한 책을 모두 점검하려 한다. 예를 들어 3번 책부터 6번 책까지를 선택했다면 3번, 4번, 5번, 6번 책을 빠짐없이 점검해야 한다. 두 책 사이의 책을 건너뛰어 선택하는 것은 허용되지 않는다. 작업 구간 밖의 책은 점검하지 않는다. 한 구간의 총점검 시간은 그 구간에 속한 각 책의 점검 시간을 모두 더한 값이다. 책 사이를 이동하거나 작업을 준비하는 시간은 별도로 들지 않는다. 총점검 시간이 T분과 정확히 같아도 선택할 수 있지만, T분을 초과하는 구간은 선택할 수 없다. 여러 구간으로 나누어 점검하는 대신 하나의 연속한 구간만 선택해야 한다. 사서는 제한 시간 안에 가능한 한 많은 책을 점검하려 한다. 점검할 수 있는 책의 수가 같은 구간이 여러 개라면 시작하는 책의 번호가 가장 작은 구간을 선택한다. 한 권도 점검할 수 없다면 아무 구간도 선택하지 않는다. 각 책의 점검 시간이 서가 순서대로 주어질 때, 선택할 구간의 책 수와 시작 번호를 구해야 한다. 모든 점검 시간은 양수이므로 구간에 책을 추가할 때 총점검 시간이 줄어드는 일은 없다.

입력

첫째 줄에 책의 수 N과 사용 가능한 시간 T가 공백으로 구분되어 주어진다. N은 1 이상 100,000 이하, T는 1 이상 1,000,000,000 이하의 정수다.
둘째 줄에 길이가 N인 문자열 D가 주어진다. D의 모든 문자는 '1'부터 '9'까지의 숫자이며, i번째 문자가 i번 책의 점검 시간을 분 단위로 나타낸다.

출력

선택한 구간에 포함된 책의 수와 시작하는 책의 번호를 공백으로 구분하여 출력한다. 시작 번호는 1부터 센다. 최대 책 수를 갖는 구간이 여러 개라면 시작 번호가 가장 작은 것을 출력한다. 한 권도 점검할 수 없다면 0 0을 출력한다.

8 10
42313241

4 1

5 2
93549

0 0

6 4
911119

4 2

출처: Devin.KR 자체 제작