지원 기록의 집중 확인 구간

문제

사내 IT 지원팀은 하루 동안 접수한 지원 요청을 접수 순서대로 정리한다. 기록에는 1번부터 N번까지 번호가 붙어 있으며, 각 기록에는 확인 점수가 적혀 있다. 확인 점수는 그 요청을 다시 살펴볼 때 점검할 항목의 수를 뜻하는 0 이상의 정수다. 점수가 0인 요청도 정상적인 기록이며 다른 기록과 똑같이 한 자리를 차지한다. 지원팀은 다음 교육 시간에 사용할 사례를 고르기 위해 기록 중 연속한 K개를 집중적으로 확인하려고 한다. 선택한 구간의 확인 점수는 그 구간에 속한 모든 기록의 점수를 더한 값이다. 담당자는 가능한 구간 중 확인 점수가 가장 큰 구간을 고른다. 교육 자료에는 접수 흐름이 그대로 드러나야 하므로, 중간 기록을 건너뛰거나 기록의 순서를 바꾸는 것은 허용하지 않는다. 구간의 길이는 반드시 K여야 하며, 더 짧거나 긴 구간으로 바꿀 수도 없다. 어떤 구간을 시작 번호 S로 나타내면 그 구간에는 S번부터 S+K-1번까지의 기록이 포함된다. 시작 번호는 1 이상이어야 하고 마지막 번호는 N 이하여야 한다. 마지막 기록 다음에 첫 번째 기록을 이어 붙이는 방식은 사용하지 않는다. 따라서 선택할 수 있는 시작 번호는 1번부터 N-K+1번까지다. 확인 점수가 가장 큰 구간이 여러 개라면 시작 번호가 가장 작은 구간을 선택한다. 모든 기록의 점수가 0인 경우에도 이 규칙을 적용한다. K가 1이면 기록 하나를 선택하는 것이고, K가 N이면 전체 기록을 선택하는 것이므로 두 경우에도 같은 계산과 선택 규칙을 따른다. 입력 조건에서 K는 항상 N 이하이므로 선택 가능한 구간은 반드시 존재한다. 선택한 구간의 시작 번호와 확인 점수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ K ≤ N ≤ 100,000이다.
둘째 줄에 각 기록의 확인 점수를 나타내는 정수 A_1, A_2, …, A_N이 공백으로 주어진다. 0 ≤ A_i ≤ 9이다.

출력

선택한 구간의 시작 번호와 그 구간의 확인 점수를 공백으로 구분하여 한 줄에 출력한다. 최대 점수가 같은 구간이 여러 개면 가장 작은 시작 번호를 출력한다.

6 3
2 0 5 1 4 0

3 10

5 2
0 0 0 0 0

1 0

4 4
3 1 0 2

1 6

출처: Devin.KR 자체 제작