//Apio 14 sequence
#include <bits/stdc++.h>
#define INF INT_MAX
#define MOD 100000007
#define MAX_N 100005
#define MAX_K 205
using namespace std;
int mg;
int N, K, a[MAX_N];
long long dpk[MAX_N], dpk1[MAX_N];
int sc[MAX_K][MAX_N];
int main(){
ios::sync_with_stdio(false);
cin>>N>>K;
if(N>10000)mg=20;
else mg=75;
for(int i=0; i<N; ++i){
cin>>a[i];
}
long long s=0;
for(int i=N-1; i>=0; --i){
s+=a[i];
dpk[i]=s*s;
sc[0][i]=N;
}
for(int k=1; k<=K; ++k){
for(int i=0; i<N; ++i)dpk1[i]=dpk[i];
s=a[N-k-1];
dpk[N-k-1]=dpk1[N-k]+s*s;
sc[k][N-k-1]=N-k;
int scc=N-k;
for(int i=N-k-2; i>=0; --i){
s+=a[i];
bool b=0;
long long sp=0;
for(int j=1; j<mg; ++j){
sp+=a[scc-j];
b=b||(scc>i+j && (s-sp)*(s-sp)+dpk1[scc-j]<=s*s+dpk1[scc]);
if(b)break;
}
//(scc>i+1 && (s-a[scc-1])*(s-a[scc-1])+dp[k-1][scc-1] <= s*s+dp[k-1][scc] )
while(b){
scc--;
s-=a[scc];
b=0;
sp=0;
for(int j=1; j<mg; ++j){
sp+=a[scc-j];
b=b||(scc>i+j && (s-sp)*(s-sp)+dpk1[scc-j]<=s*s+dpk1[scc]);
if(b)break;
}
}
dpk[i]=s*s+dpk1[scc];
sc[k][i]=scc;
}
}
s=0;
for(int i=0; i<N; ++i)s+=a[i];
cout<<(s*s-dpk[0])/2<<endl;
int cur=0;
for(int i=0; i<K; ++i){
cout<<sc[K-i][cur]<<" ";
cur=sc[K-i][cur];
}
return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/
