#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
int n,k;
cin>> n>> k;
vector<int> a(n+1), p(n+1, 0);
for (int i=1; i<=n; i++) cin>> a[i], p[i] = p[i-1]+a[i];
vector<vector<int>> dp(k+1, vector<int>(n+1, 0));
vector<vector<int>> bt(k+1, vector<int>(n+1));
for (int par=1; par<=k; par++) {
for (int i=1; i<n; i++) {
for (int j=i; j<n; j++) {
int val = dp[par-1][i-1]+(p[j]-p[i-1])*(p[n]-p[j]);
if (dp[par][j] < val) {
dp[par][j] = val;
bt[par][j] = i-1;
}
}
}
}
int ans=0, id=-1;
for (int i=1; i<n; i++) {
if (ans <= dp[k][i]) {
ans = dp[k][i];
id = i;
}
}
vector<int> pos;
int cur=k;
while (cur>0) {
int idx = bt[cur][id];
pos.push_back(id);
id = idx;
cur--;
}
reverse(pos.begin(), pos.end());
cout<< ans<< '\n';
for (int i=0; i<(int)pos.size(); i++) {
if (pos[i] == 0) cout<<i+1<< ' ';
else cout<< pos[i]<< ' ';
}
}
