점검 예산 안의 접속 기록

문제

한 게임 서버는 접속 기록을 발생 순서대로 보관한다. 운영자는 기록 일부를 골라 한 번에 점검하려 한다. 기록마다 점검에 필요한 작업량이 정수로 정해져 있으며, 작업량이 0인 기록도 있다. 작업량이 0이라는 것은 해당 기록을 확인할 때 추가 작업이 필요하지 않다는 뜻이며, 그 기록도 선택한 기록 수에는 포함된다. 점검 도구는 기록을 중간에서 건너뛰어 읽을 수 없다. 따라서 기록을 선택하려면 시작 번호와 끝 번호를 하나씩 정하고, 두 번호 사이의 모든 기록을 함께 선택해야 한다. 기록 번호는 입력된 순서대로 1부터 N까지다. 선택한 기록들의 작업량 합이 점검 예산 B 이하일 때만 점검을 실행할 수 있다. 작업량 합이 B와 정확히 같은 경우에도 실행할 수 있다. 운영자는 예산 안에서 가능한 한 많은 기록을 점검하려 한다. 조건을 만족하는 구간이 여러 개라면 기록 수가 가장 많은 구간을 고른다. 기록 수까지 같다면 시작 번호가 가장 작은 구간을 고른다. 구간은 반드시 하나 이상의 기록을 포함해야 하며, 마지막 기록 다음에 첫 번째 기록이 이어지는 것으로 보지 않는다. 선택한 구간의 기록 수와 시작 번호를 구하는 프로그램을 작성하라. 예산이 0이어도 작업량이 0인 기록으로 이루어진 구간을 선택할 수 있다. 반대로 어떤 기록 하나도 예산 안에서 점검할 수 없다면 선택 가능한 구간이 없는 것으로 처리한다. 이때는 기록 수와 시작 번호를 모두 0으로 출력한다. 기록의 작업량은 점검 과정에서 변하지 않으며, 서로 다른 구간의 작업량을 합쳐 예산과 비교하지 않는다.

입력

첫째 줄에 정수 N과 B가 공백으로 주어진다. 1 ≤ N ≤ 100,000, 0 ≤ B ≤ 1,000,000,000이다.
둘째 줄에 각 기록의 작업량을 나타내는 정수 A1, A2, ..., AN이 공백으로 주어진다. 모든 i에 대해 0 ≤ Ai ≤ 2이다.

출력

선택한 구간의 기록 수와 시작 번호를 공백으로 구분하여 한 줄에 출력한다. 선택 가능한 구간이 없다면 0 0을 출력한다.

6 4
2 1 3 0 2 1

3 2

4 0
1 2 1 2

0 0

5 0
0 0 1 0 0

2 1

출처: Devin.KR 자체 제작