#include<stdio.h>
#include<iostream>
using namespace std;
typedef long long int lld;
#define INF 1000000000000000000
lld DP[200000][300];
lld sq(lld x){
return x*x;
}
int best[200000][300];
lld acc[200000];
void computeDP(int a, int b,int parts, int l,int r){
if(a>b)return;
int mid=(a+b)/2;
for(int i=l;i<=min(r,mid);i++){
if(DP[mid][parts]>DP[i][parts-1]+sq(acc[i]-acc[mid])){
best[mid][parts]=i;
DP[mid][parts]=DP[i][parts-1]+sq(acc[i]-acc[mid]);
}
}
computeDP(a,mid-1,parts,l,best[mid][parts]);
computeDP(mid+1,b,parts,best[mid][parts],r);
}
int main(){
int n,k;
//scanf("%d %d",&n,&k);
cin>>n>>k;
lld arr[n];
for(int i=0;i<n;i++){
//scanf("%lld",&arr[i]);
cin>>arr[i];
}
acc[0]=0;
for(int i=0;i<n;i++){
acc[i+1]=acc[i]+arr[i];
}
for(int i=0;i<=n;i++){
for(int j=0;j<=k+1;j++){
DP[i][j]=INF;
}
}
DP[0][0]=0;
/*for(int parts=0;parts<=k;parts++){
for(int i=0;i<n;i++){
for(int j=i+1;j<=n;j++){
if(DP[j][parts+1]>DP[i][parts]+sq(acc[j]-acc[i])){
DP[j][parts+1]=DP[i][parts]+sq(acc[j]-acc[i]);
prev[j][parts+1]=i;
}
}
}
}*/
/*for(int parts=0;parts<=k+1;parts++){
for(int i=0;i<=n;i++){
printf("%d ",prev[i][parts]);
}printf("\n");
}*/
for(int i=1;i<=k+1;i++){
computeDP(0,n,i,0,n);
}
lld ans=sq(acc[n])-DP[n][k+1];
ans/=2;
//printf("%lld\n",ans);
cout<<ans<<endl;
int index=n;
int partition=k+1;
while(index>0){
index=best[index][partition];
partition--;
if(index>0){
printf("%d ",index);
cout<<index<<" ";
}
}cout<<endl;
//printf("\n");
return 0;
}
