#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const ll inf = 1e10;
const int maxn = 1100;
ll arr[maxn], pref[maxn];
ll dp[maxn][210], n, k;
ll parent[maxn][210];
ll getsum(int l, int r) {
if(r < l) return 0;
return pref[r] - pref[l-1];
}
int main() {
cin>>n>>k;
for(int i=1;i<=n;i++) {
cin>>arr[i];
pref[i] = pref[i-1] + arr[i];
}
for(int i=1;i<n;i++) {
dp[i][1] = pref[i] * getsum(i+1, n);
}
ll result = -inf;
int resultind = -1;
for(int d=2;d<=k;d++) {
for(int i=d;i<=n;i++) {
dp[i][d] = -inf;
for(int j=d-1;j<i;j++) {
if(dp[j][d-1] + getsum(j+1, i) * getsum(i+1, n) >= dp[i][d]) {
dp[i][d] = dp[j][d-1] + getsum(j+1, i) * getsum(i+1, n);
parent[i][d] = j;
}
}
}
}
for(int i=1;i<=n;i++) {
if(dp[i][k] >= result) {
result = dp[i][k];
resultind = i;
}
}
vector<int>v;
cout<<result<<"\n";
for(int i=k;i>=1;i--) {
v.pb(resultind);
resultind = parent[resultind][i];
}
reverse(v.begin(), v.end());
for(int i:v)
cout<<i<<" ";
cout<<"\n";
}
