충전소 집중 운영 구간

문제

전기차 충전소는 차량에 전기를 공급하기도 하고, 연결된 차량에서 전기를 돌려받기도 한다. 운영자는 하루 중 연속된 일정 시간에 관리 인력을 집중 배치하려 한다. 이를 위해 하루를 길이가 같은 N개의 시간 칸으로 나누고, 각 시간 칸의 순공급량을 정수로 기록했다. 순공급량은 차량에 공급한 전력량에서 차량으로부터 돌려받은 전력량을 뺀 값이다. 따라서 양수는 공급이 더 많았음을, 음수는 회수가 더 많았음을 뜻하며, 두 양이 같으면 0이다. 모든 기록은 같은 전력량 단위를 사용한다. 집중 운영 구간은 정확히 K개의 연속된 시간 칸으로 정해야 한다. 시작 시간 칸이 s이면 s번부터 s+K-1번까지가 하나의 후보 구간이다. 시간 칸에는 1번부터 N번까지 번호가 붙어 있고, 마지막 시간 칸 뒤에 첫 시간 칸이 이어지는 것으로 보지 않는다. 따라서 가능한 시작 번호는 1 이상 N-K+1 이하이다. 서로 다른 시작 번호로 정한 구간은 포함하는 시간 칸이 일부 겹치더라도 서로 다른 후보로 센다. 한 후보 구간의 점수는 그 안에 있는 모든 시간 칸의 순공급량을 더한 값이다. 운영자는 점수가 가장 큰 구간에 인력을 배치하려 한다. 음수 기록이 포함되어 있어도 구간의 길이를 줄이거나 그 기록을 제외할 수 없다. 모든 후보의 점수가 음수이면 그중 가장 큰 음수 점수가 최적 점수이다. 아무 구간도 선택하지 않는 선택지는 없다. 운영 계획을 작성하려면 최적 점수뿐 아니라 그 점수를 얻는 후보가 몇 개인지도 알아야 한다. 또한 최적 후보가 여러 개이면 가장 먼저 시작하는 후보를 실제 배치 구간으로 사용한다. 전체 기록을 바탕으로 최적 점수, 실제 배치 구간의 시작 번호, 최적 점수를 얻는 후보 수를 구한다. K는 항상 N 이하이므로 후보 구간은 적어도 하나 존재한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 50,000이다.
둘째 줄에 시간 칸 1번부터 N번까지의 순공급량 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 각 A_i는 -1,000 이상 1,000 이하의 정수이다.

출력

최적 점수, 최적 점수를 얻는 구간 중 가장 작은 시작 번호, 최적 점수를 얻는 구간 수를 공백으로 구분하여 한 줄에 출력한다.

7 3
4 -2 3 1 -1 5 -3

5 1 2

4 2
-5 -2 -2 -6

-4 2 1

3 3
0 0 0

0 1 1

출처: Devin.KR 자체 제작