#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<ll> v(n);
for(int i = 0; i < n; i++) cin >> v[i];
vector<ll> pre(n);
for(int i = 0; i < n; i++) {
pre[i] = v[i];
if(i) pre[i] += pre[i - 1];
}
auto get_sum = [&](int l, int r) -> ll {
ll ret = pre[r];
if(l) ret -= pre[l - 1];
return ret;
};
vector<vector<ll>> dp(n, vector<ll>(k + 1, -1e9));
vector<vector<int>> from(n, vector<int>(k + 1, -1));
for(int i = 0; i < n; i++) dp[i][0] = 0;
for(int i = 0; i < n; i++) {
for(int j = 1; j <= k; j++) {
// int l = 0, r = i - 1;
// for(int c = 0; c < 300; c++) {
// int mid1 = (l + l + r) / 3, mid2 = (l + r + r) / 3;
// ll val1 = dp[mid1][j - 1] + get_sum(0, mid1) * get_sum(mid1 + 1, i);
// ll val2 = dp[mid2][j - 1] + get_sum(0, mid2) * get_sum(mid2 + 1, i);
// if(val1 < val2) l = mid1;
// else r = mid2;
// }
// for(int h = l; h <= r; h++) {
// if(dp[h][j - 1] == -1e9) continue;
// ll val = dp[h][j - 1] + get_sum(0, h) * get_sum(h + 1, i);
// if(val >= dp[i][j]) {
// from[i][j] = h;
// dp[i][j] = val;
// }
// }
for(int t = i; t >= 1; t--) {
if(dp[t - 1][j - 1] == -1e9) continue;
ll val = dp[t - 1][j - 1] + get_sum(0, t - 1) * get_sum(t, i);
if(val >= dp[i][j]) {
from[i][j] = t - 1;
dp[i][j] = val;
}
}
}
}
cout << dp[n - 1][k] << "\n";
vector<int> ans;
int cur = n - 1, curk = k;
while(curk) {
cur = from[cur][curk];
ans.push_back(cur);
curk--;
}
reverse(ans.begin(), ans.end());
for(int x : ans) cout << x + 1 << " ";
return 0;
}
