#include <cstdio>
typedef long long ll;
int n,k;
int d[100010];
ll prefix[100010];
ll dp[2][100010];
ll *dp_bef, *dp_cur;
int chosen[201][100010];
int* chosen_arr;
struct tp{
ll a,b,c;
tp cross(const tp& other) const {
return {b*other.c-c*other.b, c*other.a-a*other.c, a*other.b-b*other.a};
}
} l[100010];
int lind[100010];
int ln;
void addLine(ll a,ll c,int ind){
tp curl={a,-1,c};
tp pa, pb;
while(ln>=2){
pa=l[ln-2].cross(l[ln-1]);
pb=l[ln-1].cross(curl);
if(pa.a*pb.c < pa.c*pb.a) break;
--ln;
}
l [ln]=curl;
lind[ln]=ind;
++ln;
}
void work(int trial){
int i;
ln=0;
addLine(0,0,0);
int lli=0;
for(i=1; i<=n; ++i){
while(lli+1<ln){
tp cp=l[lli].cross(l[lli+1]);
if(cp.a <= cp.c * prefix[i]) ++lli;
else break;
}
dp_cur[i] = l[lli].a*prefix[i] + l[lli].c;
chosen[trial][i]=lind[lli];
addLine(prefix[i], dp_bef[i]-prefix[i]*prefix[i], i);
}
}
int ans[201];
int main()
{
scanf("%d%d",&n,&k);// ++k;
int i;
for(i=1;i<=n;++i) scanf("%d",d+i), prefix[i]=prefix[i-1]+d[i];
dp_bef=dp[0], dp_cur=dp[1];
for(i=1;i<=k;++i){
chosen_arr=chosen[i];
work(i);
auto tmp=dp_cur; dp_cur=dp_bef; dp_bef=tmp;
}
printf("%lld\n",dp_bef[n]);
int j;
i=k; j=n;
while(true){
ans[i]=j;
if(i==0) break;
j=chosen[i--][j];
}
for(i=0; i<k; ++i) printf("%d ",ans[i]);
return 0;
}
