#include<stdio.h>
#define MaxN 100001
typedef long long int lint;
typedef struct Line{
lint m;
lint b;
int from;
Line(){m=b=from=0;}
Line(lint _m,lint _b,int _from){m=_m;b=_b;from=_from;}
}line;
line l[MaxN];
int ans[220][MaxN],p,sz;
int dy1[MaxN],dy2[MaxN];
int n,c;
lint sum[MaxN];
double cross(line i,line j){return (double)(i.b-j.b)/(j.m-i.m);}
void push(line t){
while(sz>=2 && cross(t,l[sz])<cross(l[sz-1],l[sz])) sz--;
l[++sz]=t;
}
int main(){
int i,j;
scanf("%d %d",&n,&c);
for(i=1; i<=n; i++){
scanf("%d",&sum[i]);
sum[i]+=sum[i-1];
}
p=1;
push(Line(0,0,0));
for(i=1; i<=c; i++){
for(j=i; j<n; j++){
while(sz-p>=1 && cross(l[p],l[p+1])<=sum[j]) p++;
dy2[j]= l[p].m*sum[j]+l[p].b + sum[j]*(sum[n]-sum[j]);
ans[i][j]=l[p].from;
}
p=1;
sz=0;
for(j=i; j<n; j++){
dy1[j]=dy2[j];
push(Line(sum[j],-sum[n]*sum[j]+dy1[j],j));
}
}
lint max_=0;
int pos,p[220],pcnt=0;
for(i=1; i<=n; i++){
if(max_<dy1[i]){
max_=dy1[i];
pos=i;
}
}
while(pos!=0){
p[++pcnt]=pos;
pos=ans[c-pcnt+1][pos];
}
printf("%lld\n",max_);
for(i=pcnt; i>=1; i--){
printf("%d ",p[i]);
}
return 0;
}
