학원의 복습 묶음

문제

한 학원에서는 지난 수업의 복습 자료를 묶어 학생들에게 나누어 주려고 한다. 수업일은 오래된 날부터 1번부터 N번까지 번호가 붙어 있다. i번 수업일의 복습 자료는 A_i장이며, 자료가 없는 수업일도 있다. 모든 장수는 0 이상의 정수다. 담당자는 정확히 K개의 연속한 수업일을 골라 하나의 복습 묶음을 만들기로 했다. 시작 수업일을 s번으로 정하면 s번부터 s+K-1번까지의 자료를 모두 넣는다. 선택한 구간 안에서 일부 수업일을 빼거나, 어느 수업일의 자료 중 일부만 넣을 수는 없다. 자료가 없는 수업일도 선택한 K개의 수업일 중 하나로 센다. 따라서 시작 번호 s는 1 이상 N-K+1 이하의 정수여야 한다. 복습 묶음을 넣을 봉투에는 자료를 최대 B장까지 넣을 수 있다. 묶음의 전체 장수가 B 이하이면 봉투에 넣을 수 있으며, 정확히 B장인 묶음도 허용한다. 담당자는 봉투에 넣을 수 있는 묶음 중 전체 장수가 가장 많은 것을 선택한다. 전체 장수가 같은 묶음이 여러 개라면 시작 수업일의 번호가 가장 작은 것을 선택한다. 수업일별 자료의 순서를 바꾸어 새로운 묶음을 만들 수는 없다. 예를 들어 자료가 없는 날이 구간에 포함되어도 그 구간의 길이는 줄어들지 않는다. 또한 B가 0이면 전체 장수가 0인 묶음만 선택할 수 있다. 이런 묶음이 여러 개라면 역시 가장 먼저 시작하는 묶음을 선택한다. 봉투에 넣을 수 있는 묶음이 하나도 없으면 선택할 수 없다는 결과를 출력한다. 수업일별 자료 장수와 K, B가 주어졌을 때, 규칙에 따라 선택할 묶음의 시작 수업일 번호와 전체 장수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, K, B가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 100,000, 1 ≤ K ≤ N, 0 ≤ B ≤ 900,000이다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 0 ≤ A_i ≤ 9이다.

출력

선택할 수 있는 묶음이 있으면 시작 수업일 번호와 전체 장수를 공백으로 구분하여 한 줄에 출력한다. 전체 장수가 최대인 묶음이 여러 개이면 시작 번호가 가장 작은 묶음을 출력한다. 선택할 수 있는 묶음이 없으면 -1만 출력한다.

8 3 10
4 2 5 1 7 0 3 6

5 10

4 2 3
2 3 2 4

-1

6 2 6
3 3 1 5 1 5

1 6

출처: Devin.KR 자체 제작