#include<stdio.h>
int n,m;
int a[100100];
long long int b[100100];
long long int dp[100100];
long long int ndp[100100];
int cutp[210][100100];
int deq[100100];
int cut[210];
int qs,qe;
int main(){
int i,j,k;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
b[i+1]=b[i]+a[i];
}
for(i=0;i<=n;i++){
dp[i]=b[i]*b[i];
}
for(i=0;i<m;i++){
ndp[0]=0;
deq[0]=0;
qs=0;
qe=1;
for(j=1;j<=n;j++){
while(qs+1<qe&&dp[deq[qs]]+(b[j]-b[deq[qs]])*(b[j]-b[deq[qs]])>=dp[deq[qs+1]]+(b[j]-b[deq[qs+1]])*(b[j]-b[deq[qs+1]]))qs++;
ndp[j]=dp[deq[qs]]+(b[j]-b[deq[qs]])*(b[j]-b[deq[qs]]);
cutp[i+1][j]=deq[qs];
while(qs+1<qe&&((long double)b[j]-b[deq[qe-1]])*(dp[deq[qe-1]]+b[deq[qe-1]]*b[deq[qe-1]]-dp[deq[qe-2]]-b[deq[qe-2]]*b[deq[qe-2]])>=((long double)b[deq[qe-1]]-b[deq[qe-2]])*(dp[j]+b[j]*b[j]-dp[deq[qe-1]]-b[deq[qe-1]]*b[deq[qe-1]]))qe--;
deq[qe]=j;
qe++;
}
for(j=0;j<=n;j++){
dp[j]=ndp[j];
}
}
printf("%lld\n",(b[n]*b[n]-dp[n])/2);
j=n;
for(i=m-1;i>=0;i--){
j=cutp[i+1][j];
cut[i]=j;
}
for(i=0;i<m;i++){
printf("%d ",cut[i]);
}
}
