#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> a(n+1), pref(n+1);
for(int i=1;i<=n;i++) {
cin >> a[i];
pref[i]=pref[i-1]+a[i];
}
const long long INF = 4e18;
vector<vector<long long>> dp(k+2, vector<long long>(n+1, INF));
vector<vector<int>> par(k+2, vector<int>(n+1));
dp[0][0]=0;
for(int j=1;j<=k+1;j++) {
for(int i=j;i<=n;i++) {
for(int p=j-1;p<i;p++) {
long long s = pref[i]-pref[p];
long long val = dp[j-1][p] + s*s;
if(val < dp[j][i]) {
dp[j][i]=val;
par[j][i]=p;
}
}
}
}
long long S = pref[n];
cout << (S*S - dp[k+1][n]) / 2 << '\n';
vector<int> ans;
int i=n, j=k+1;
while(j>1) {
int p = par[j][i];
ans.push_back(p);
i=p;
j--;
}
reverse(ans.begin(), ans.end());
for(int i=0;i<ans.size();i++) {
cout << ans[i] << (i+1==ans.size()?'\n':' ');
}
return 0;
}
