수열 나누기

음이 아닌 정수 $n$개로 이루어진 수열을 $k+1$개의 비어 있지 않은 연속 부분으로 나눈다. 나누기를 $k$번 수행하고, 한 번 나눌 때마다 새로 생긴 두 부분의 원소 합을 곱한 값을 점수로 받는다. 나누는 순서는 최종 점수에 영향을 주지 않는다. 받을 수 있는 점수의 최댓값과 그를 만드는 나누기 위치를 구한다.

첫 줄에 $n$, $k$가 주어진다. ($2 \le n \le 100000$, $1 \le k \le \min(n-1, 200)$) 둘째 줄에 음이 아닌 정수 $a_1, \ldots, a_n$ ($0 \le a_i \le 10^4$)이 주어진다.

첫 줄에 최대 점수를 출력한다. 둘째 줄에 나누기 위치를 순서대로 출력한다. 여러 답이 있으면 아무거나 출력한다.