주차장 임시 작업 구역

문제

한 주차장에는 일직선으로 이어진 N개의 주차 칸이 있다. 칸에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 관리인은 바닥 표시를 새로 칠하기 위해 정확히 K개의 연속한 칸을 임시 작업 구역으로 지정하려 한다. 주차장의 양 끝은 연결되어 있지 않으므로 N번 칸 다음에 1번 칸을 이어서 작업 구역을 만들 수는 없다. 각 칸의 상태는 정수 하나로 주어진다. 값이 -1이면 옮길 수 없는 시설물이 놓인 칸이다. 값이 0이면 비어 있는 칸이다. 양수이면 차량이 주차되어 있으며, 그 값은 해당 차량을 다른 곳으로 옮길 때 드는 비용이다. 시설물이 놓인 칸은 작업 구역에 포함할 수 없다. 차량이 있는 칸은 차량을 옮긴 뒤 작업 구역에 포함할 수 있다. 작업 구역 밖에 있는 차량은 옮길 필요가 없다. 작업 구역을 정하면 그 안에 있는 모든 차량을 옮겨야 한다. 필요한 총비용은 작업 구역에 속한 칸들의 값의 합이다. 빈 칸은 비용에 영향을 주지 않는다. 차량을 옮길 별도의 공간은 충분하므로 다른 주차 칸의 상태나 차량을 옮기는 순서는 고려하지 않는다. 시설물만 포함하지 않는다면 어떤 연속한 K개의 칸도 작업 구역으로 선택할 수 있다. 관리인은 총비용이 가장 작은 작업 구역을 선택한다. 총비용이 같은 작업 구역이 여러 개라면 시작 칸의 번호가 가장 작은 것을 선택한다. 선택한 작업 구역의 시작 칸 번호와 총비용을 구하는 프로그램을 작성한다. 시설물 때문에 가능한 작업 구역이 하나도 없다면 정해진 실패 표시를 출력한다.

입력

첫째 줄에 정수 N과 K가 주어진다. 1 ≤ K ≤ N ≤ 10,000이며 K ≤ 20이다.
둘째 줄에 각 칸의 상태를 나타내는 정수 A_1, A_2, ..., A_N이 주어진다. 각 A_i는 -1 또는 0 이상 99 이하의 정수이다.

출력

가능한 작업 구역이 있으면 선택한 시작 칸 번호와 총비용을 공백으로 구분하여 출력한다. 가능한 작업 구역이 없으면 -1 하나만 출력한다.

8 3
5 0 2 -1 1 0 3 0

6 3

5 2
0 2 0 2 0

1 2

4 2
-1 0 -1 3

-1

출처: Devin.KR 자체 제작