두 번의 충전 안내 시간

문제

전기차 충전소는 하루 운영 시간을 같은 길이의 N개 시간대로 나누어 관리한다. 시간대에는 이른 순서대로 1번부터 N번까지 번호가 붙어 있다. 충전소는 이용자가 많이 찾는 시간에 직원이 충전 방법을 안내하도록, 하루에 정확히 두 개의 안내 구간을 정하려고 한다. 안내 구간 하나는 연속한 L개의 시간대로 이루어진다. 구간을 시작한 뒤 중간에 안내를 멈추거나 길이를 바꿀 수 없다. 두 구간은 같은 시간대를 포함해서는 안 되지만, 첫 구간이 끝난 바로 다음 시간대에 두 번째 구간이 시작하는 것은 가능하다. 운영 시간이 끝난 뒤 다음 날로 이어지는 구간은 허용하지 않는다. 각 시간대에는 안내를 받을 것으로 예상되는 이용자 수가 정수로 주어진다. 다만 설비 점검으로 안내가 불가능한 시간대는 이용자 수 대신 -1로 표시한다. 안내 구간에는 -1인 시간대를 하나도 포함할 수 없다. 이용자 수가 0인 시간대는 안내가 가능하며, 단지 그 시간대에 안내를 받을 예상 이용자가 없다는 뜻이다. 두 안내 구간의 예상 이용자 수는 두 구간에 포함되는 모든 시간대의 이용자 수를 더한 값이다. 충전소는 이 값이 최대가 되도록 두 구간을 선택한다. 선택 결과는 시작 번호가 작은 구간을 첫 번째 구간, 나머지를 두 번째 구간으로 적는다. 최대 이용자 수를 얻는 선택이 여러 개라면 첫 번째 구간의 시작 번호가 가장 작은 선택을 사용한다. 이 번호도 같으면 두 번째 구간의 시작 번호가 가장 작은 선택을 사용한다. 시간대별 정보와 L이 주어졌을 때 두 구간의 시작 번호와 최대 예상 이용자 수를 구한다. 안내 가능한 구간이 하나뿐인 경우를 포함하여, 조건을 만족하는 두 구간을 정할 수 없다면 -1만 출력한다. 가능한 두 구간의 예상 이용자 수가 0이라면 정상적인 선택 결과를 출력해야 한다.

입력

첫째 줄에 시간대 수 N과 안내 구간의 길이 L이 공백으로 구분되어 주어진다. 두 값은 정수이며 1 ≤ N ≤ 300, 1 ≤ L ≤ N을 만족한다.
둘째 줄에 1번부터 N번까지 시간대별 값이 공백으로 구분되어 주어진다. 각 값은 -1 또는 0 이상 1,000,000 이하의 정수다. -1은 해당 시간대에 안내가 불가능함을 뜻한다.

출력

가능한 선택이 있으면 첫 번째 구간의 시작 번호, 두 번째 구간의 시작 번호, 최대 예상 이용자 수를 공백으로 구분하여 한 줄에 출력한다. 조건을 만족하는 두 구간이 없으면 -1만 출력한다.

8 2
3 4 -1 2 8 1 5 5

4 7 20

6 2
0 0 0 0 0 0

1 3 0

5 2
4 -1 7 8 -1

-1

출처: Devin.KR 자체 제작