#include<bits/stdc++.h>
using namespace std;
const int nax = 1005;
const long long INF = 1e15;
int n, k;
long long dp[nax][203];
long long a[nax], to[nax][203];
vector<int>config;
long long solve(int i, int j) {
if(i>n) {
if(j==k+2) return 0;
return INF;
}
long long &ret = dp[i][j];
if(ret!=-1) return ret;
ret = INF;
long long cur = 0, sub = 0;
for(int p=i; p<=n; ++p) {
cur += a[p];
sub += a[p] * a[p];
long long cand = cur * cur - sub + solve(p+1, j+1);
if(cand < ret) {
ret = cand;
to[i][j] = p;
}
}
return ret;
}
void construct(int i, int j) {
if(i>n) return;
if(to[i][j]<n) config.push_back(to[i][j]);
construct(to[i][j]+1, j+1);
}
void PlayGround() {
cin>>n>>k;
for(int i=1; i<=n; ++i) {
cin>>a[i];
}
long long S = accumulate(a+1, a+n+1, 0LL);
long long base = 0;
for(int i=1; i<=n; ++i) {
base += (S-a[i]) * a[i];
}
memset(dp, -1, sizeof dp);
cout<<(base - solve(1, 1)) / 2<<'\n';
construct(1, 1);
for(int x : config) {
cout<<x<<' ';
}
cout<<'\n';
// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
