#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
ll S[100005];
ll DP1[100005];
ll DP2[100005];
int BES[205][100005];
const ll INF = 1e18;
void fill(int lev, int l, int r, int optl, int optr) {
if (l > r) return;
optr = min(optr,r);
int m = (l+r)/2;
DP2[m] = 1e18;
int bes = -1;
FOR(i,optl,min(optr+1,m)) {
ll tmp = (S[m] - S[i])*(S[m] - S[i])+DP1[i];
if ((S[m] - S[i])*(S[m] - S[i])+DP1[i] <= DP2[m]) {
DP2[m] = (S[m] - S[i])*(S[m] - S[i])+DP1[i];
bes = i;
}
}
BES[lev][m] = bes;
fill(lev, l,m-1,optl,bes);
fill(lev, m+1,r,bes,optr);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
S[0] = 0;
int N, K; cin >> N >> K;
for (int i = 1; i <= N; i++){
ll x; cin >> x;
S[i] = S[i - 1] + x;
}
for (int i = 1; i <= N; i++){
DP2[i] = S[i]*S[i];
}
for (int j = 2; j <= K + 1; j++){
for (int i = 1; i <= N; i++){
DP1[i] = DP2[i];
}
fill(j, 1, N, 1, N);
}
int curpos = N;
vector<int> idx;
for (int j = K + 1; j >= 2; j--){
idx.push_back(BES[j][curpos]);
curpos = BES[j][curpos];
}
reverse(idx.begin(), idx.end());
cout << (S[N] * S[N] - DP2[N])/2 << endl;
for (int j: idx){
cout << j << ' ';
}
cout << endl;
}
