#include<stdio.h>
int n, k, w[101000], top;
int Path[210][101000];
long long S[101000], D[2][101000];
struct Stack{
long long a, b;
int pv;
}st[101000];
void Add(long long a, long long b, int pv){
while (top > 1 && (double)(st[top - 1].b - b) / (a - st[top - 1].a) <= (double)(st[top - 1].b - st[top].b) / (st[top].a - st[top - 1].a))top--;
if (top && st[top].a == a){
if (st[top].b < b)st[top].b = b;
return;
}
top++;
st[top].a = a, st[top].b = b, st[top].pv = pv;
}
long long Gap(int t, long long x){
return st[t].a*x + st[t].b;
}
long long Do(long long x){
int be = 1, ed = top - 1, mid, r = top;
while (be <= ed){
mid = (be + ed) >> 1;
if (Gap(mid, x) >= Gap(mid + 1, x)){
r = mid;
ed = mid - 1;
}
else{
be = mid + 1;
}
}
return r;
}
int Ans[210];
int main(){
int i, j, t, pv = 0;
scanf("%d%d", &n, &k);
k++;
for (i = 1; i <= n; i++){
scanf("%d", &w[i]);
S[i] = S[i - 1] + w[i];
}
for (i = 2; i <= k; i++){
top = 0;
pv = !pv;
for (j = i; j <= n; j++){
Add(S[j - 1], D[!pv][j - 1] - S[j - 1] * S[j - 1], j - 1);
t = Do(S[j]);
D[pv][j] = Gap(t, S[j]);
Path[i][j] = st[t].pv;
}
}
printf("%lld\n", D[pv][n]);
t = n;
for (i = k; i >= 2; i--){
t = Path[i][t];
Ans[i] = t;
}
for (i = 2; i <= k; i++)printf("%d ", Ans[i]);
}
