#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=1e5+50,inf=1e5;
int n,K,a[N],dp[N][201],pref[N];
int parent[N][201];
/*int root,nc,lc[2*N],rc[2*N],sum[2*N],sum1[2*N],lazy[2*N];
void pull(int c){
sum1[c]=sum1[lc[c]]+sum1[rc[c]];
sum[c]=sum[lc[c]]+sum[rc[c]]+sum1[c]*sum1[c]-sum1[lc[c]]*sum1[lc[c]]-sum1[rc[c]]*sum1[rc[c]];
}
void update(int c,int qval){
sum[c]+=qval*qval+2*sum1[c]*qval;
sum1[c]+=qval;
lazy[c]+=qval;
}
void push(int c){
update(lc[c],lazy[c]);
update(rc[c],lazy[c]);
lazy[c]=0;
}
void Build(int &c,int ss,int se,int k){
if(!c) c=++nc;
sum[c]=sum1[c]=lazy[c]=0;
if(ss==se){
sum[c]=dp[ss][k];
return;
}
int mid=ss+se>>1;
Build(lc[c],ss,mid,k),Build(rc[c],mid+1,se,k);
pull(c);
}
void Update(int &c,int ss,int se,int qs,int qe,int qval){
if(qs>qe) return;
if(qs<=ss && se<=qe){
update(c,qval);
return;
}
if(qe<ss || se<qs) return;
int mid=ss+se>>1;
push(c);
Update(lc[c],ss,mid,qs,qe,qval),Update(rc[c],mid+1,se,qs,qe,qval);
pull(c);
}
int Get(int c,int ss,int se,int qs,int qe){
if(qs>qe) return inf;
if(qs<=ss && se<=qe) return sum[c];
if(qe<ss || se<qs) return inf;
int mid=ss+se>>1;
push(c);
return min(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}*/
int Cost(int l,int r){return (pref[r]-pref[l-1])*(pref[r]-pref[l-1]);}
void Solve(int l,int r,int L,int R,int k){
if(l>r) return;
int mid=l+r>>1;
int ind=L;
dp[mid][k]=inf;
for(int i=min(mid-1,R);i>=L;i--){
if(dp[mid][k]>dp[i][k-1]+Cost(i+1,mid)){
dp[mid][k]=dp[i][k-1]+Cost(i+1,mid);
ind=i;
}
}
parent[mid][k]=ind;
Solve(l,mid-1,L,ind,k);
Solve(mid+1,r,ind,R,k);
}
int main(){
scanf("%i%i",&n,&K);
for(int i=1;i<=n;i++) scanf("%i",&a[i]);
for(int i=1;i<=n;i++) pref[i]=pref[i-1]+a[i];
for(int i=0,sum=0;i<=n;i++) sum+=a[i],dp[i][0]=sum*sum;
/*for(int k=1;k<=K;k++){
Build(root,0,n,k-1);
dp[0][k]=inf;
for(int i=0;i<=n;i++) printf("%i ",Get(root,0,n,i,i));
printf("\n");
for(int i=1;i<=n;i++){
Update(root,0,n,0,i-1,a[i]);
dp[i][k]=Get(root,0,n,0,i-1);
for(int i=0;i<=n;i++) printf("%i ",Get(root,0,n,i,i));
printf("\n");
//for(int j=i-1,sum=0;j>=0;j--){
//sum+=a[j+1];
//dp[i][k]=min(dp[i][k],dp[j][k-1]+sum*sum);
//}
}
printf("\n");
}
for(int k=0;k<=K;k++){printf("%i: ",k);for(int i=0;i<=n;i++){printf("%i ",dp[i][k]);}printf("\n");}*/
for(int k=1;k<=K;k++){
Solve(1,n,0,n,k);
}
int res=0;
for(int i=1;i<=n;i++) res+=a[i];
res=(res*res-dp[n][K])/2;
printf("%i\n",res);
vector<int>ans;
int temp=K,nesto=n;
while(temp>0){
ans.pb(parent[nesto][temp]);
nesto=parent[nesto][temp];
temp--;
}
for(auto i:ans) printf("%i ",i);
printf("\n");
return 0;
}
