// "I assure you that you guys won't make it to the top 4"
// - Tzaph, 21 December 2021
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll long long
#define ld long double
#define si short int
#define i8 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define psi pair<si, si>
#define pi8 pair<i8, i8>
#define pq priority_queue
#define fi first
#define se second
#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'
#define yume using
#define wo namespace
#define kanaeyo std
yume wo kanaeyo;
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}
const ll ModA = 998244353;
const ll ModC = 1e9 + 7;
const ll INF = 1e18;
const ll iINF = 1e9;
const ld EPS = 1e-9;
const ld iEPS = 1e-6;
const ll maxK = 202, maxN = 1e5 + 1;
ll n, k, a[maxN], pf[maxN];
ll dp[maxK][maxN], pred[maxK][maxN];
ll pref(ll l, ll r) {
return pf[r] - pf[l-1];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> k;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
pf[i] = pf[i-1] + a[i];
}
for (ll i = 1; i <= n; i++) {
dp[0][i] = -INF;
}
for (ll x = 1; x <= k+1; x++) {
for (ll i = 1; i <= n; i++) {
dp[x][i] = -INF;
if (i >= x) {
for (ll j = x-1; j < i; j++) {
ll cur = dp[x-1][j] + 1ll * pref(1, j) * pref(j+1, i);
if (cur > dp[x][i]) {
dp[x][i] = cur;
pred[x][i] = j;
}
}
}
}
}
cout << dp[k+1][n] << '\n';
for (ll i = k+1, cur = n; i > 1; i--) {
cout << pred[i][cur] << ' ';
cur = pred[i][cur];
}
cout << '\n';
}
