#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vint = vector<int>;
using vll = vector<ll>;
using pint = pair<int, int>;
using vpint = vector<pint>;
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a)-1; i >= (b); i--)
const ll INF = 1e18;
void solve() {
int n, k; cin >> n >> k;
vint a(n); rep(i, n) cin >> a[i];
vint prefix(n);
rep(i, n) prefix[i] = i == 0 ? a[i] : a[i] + prefix[i-1];
vint suffix(n);
rrep(i, n) suffix[i] = i == n-1 ? 0 : a[i+1] + suffix[i+1];
vector<vll> dp(k, vll(n-1, -INF));
vector<vint> dp_i(k, vint(n-1));
rep(l, k) {
rep(i, n-1) {
if (l == 0) dp[l][i] = (ll)prefix[i]*suffix[i];
else {
int prefix_val = a[i];
RFOR(j, i, l-1) {
if (dp[l][i] < dp[l-1][j] + (ll)prefix_val*suffix[i]) {
dp[l][i] = dp[l-1][j] + (ll)prefix_val*suffix[i];
dp_i[l][i] = j;
}
prefix_val += a[j];
}
}
}
}
ll res = -INF, res_i = -1;
FOR(i, k-1, n-1) if (res < dp[k-1][i]) res = dp[k-1][i], res_i = i;
cout << res << endl;
vint pos(k);
rrep(i, k)
pos[i] = res_i, res_i = dp_i[i][res_i];
rep(i, k) cout << pos[i]+1 << " ";
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
