//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
const ll N = 2e2 + 10;
ll n, k;
ll dp[N][N][N];
pair<int, int> p[N][N][N];
bool was[N][N][N];
ll a[N];
ll sum(ll l, ll r) {
return a[r] - a[l - 1];
}
ll calc(ll l, ll r, ll k) {
if(k == 0)
return 0;
if(was[l][r][k])
return dp[l][r][k];
was[l][r][k] = 1;
for(int i = l; i < r; i++) {
for(int j = 0; j < k; j++) {
if(i - l < j || r - i - 1 < k - j - 1)
continue;
ll z = sum(l, i) * sum(i + 1, r) + calc(l, i, j) + calc(i + 1, r, k - j - 1);
if(dp[l][r][k] < z)
dp[l][r][k] = z, p[l][r][k] = mp(i, j);
}
}
return dp[l][r][k];
}
int main() {
speed;
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
a[i] += a[i - 1];
}
cout << calc(1, n, k) << '\n';
assert(dp[1][n][k] != 0);
vector<pair<int, pair<int ,int>>> q;
vector<int> raz;
q.pb(mp(k, mp(1, n)));
while((ll)q.size()) {
ll L = q.back().s.f, R = q.back().s.s, rp = q.back().f;
//cout << L << " " << R << " " << rp << " " << p[L][R][rp].f << " " << p[L][R][rp].s << '\n';
q.pop_back();
if(rp == 0)
continue;
raz.pb(p[L][R][rp].f);
//cout << L << " " << p[L][R][rp].f << '\n';
//cout << p[L][R][rp].f + 1 << " " << R << '\n';
q.pb(mp(p[L][R][rp].s, mp(L, p[L][R][rp].f)));
q.pb(mp(rp - p[L][R][rp].s - 1, mp(p[L][R][rp].f + 1, R)));
//cnt++;
//if(cnt == 5)
// exit(0);
}
sort(raz.begin(), raz.end());
for(auto u : raz)
cout << u << " ";
}
/*
7 3
4 1 3 4 0 2 3
*/
