#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;
typedef long long ll;
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
int n, k;
int pre[N];
vector<int> res;
map<int, ll> dp[N];
map<int, int> trace[N];
ll compute(int l, int r, int level) {
if (level >= k || l >= r) return 0LL;
ll res = dp[l][r];
if (res) return res;
for (int i = l; i < r; i ++) {
ll tmp = 1LL * (pre[i] - pre[l - 1]) * (pre[r] - pre[i]);
if (maximize(res, compute(l, i, level + 1) + compute(i + 1, r, level + 1) + tmp))
trace[l][r] = i;
}
return dp[l][r] = res;
}
void retrace(int l, int r, int level) {
if (l >= r || level >= k) return;
int m = trace[l][r];
res.push_back(m);
retrace(l, m, level + 1);
retrace(m + 1, r, level + 1);
}
void solve(void) {
cin >> n >> k;
for (int i = 1; i <= n; i ++) {
int x; cin >> x;
pre[i] = pre[i - 1] + x;
}
cout << compute(1, n, 1) << '\n';
retrace(1, n, 1);
for (int x: res) cout << x << " ";
}
int main(void) {
cin.tie(0)->sync_with_stdio(0);
int test = 1;
// cin >> test;
while (test --) {
solve();
}
return 0;
}
