#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using i64 = long long;
const int MAXN = 1e4 + 5;
const int MAXK = 205;
#define ALL(a) (a).begin(), (a).end()
int N, K;
int a[MAXN];
i64 prefix[MAXN];
struct Line {
mutable long long k, m, p;
bool operator<(const Line& o) const {
return k < o.k;
}
bool operator<(long long x) const {
return p < x;
}
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const long long inf = LLONG_MAX;
long long div(long long a, long long b) { // floored division
return a / b - ((a ^ b) < 0 && a % b);
}
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(long long k, long long m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
long long query(long long x) {
assert(!empty());
auto l = *lower_bound(x);
return l.k * x + l.m;
}
};
namespace subtask {
i64 dp[MAXN][MAXK];
pii trace[MAXN][MAXK];
void solution() {
K++;
memset(dp, -0x3f, sizeof dp);
dp[0][0] = 0;
for(int z = 1; z <= K; z++) {
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= i; j++) {
if(dp[i][z] < dp[j - 1][z - 1] + prefix[i] * prefix[N] - prefix[i] * prefix[i] - prefix[j - 1] * prefix[N] + prefix[j - 1] * prefix[i]) {
dp[i][z] = dp[j - 1][z - 1] + prefix[i] * prefix[N] - prefix[i] * prefix[i] - prefix[j - 1] * prefix[N] + prefix[j - 1] * prefix[i];
trace[i][z] = {j - 1, z - 1};
}
}
}
}
pii cur = {N, K};
printf("%lld\n", dp[N][K]);
for(int i = 1; i < K; i++) {
cur = trace[cur.first][cur.second];
printf("%d ", cur.first);
}
}
}
signed main() {
#define TASK "code"
if (fopen(TASK ".inp", "r")) {
freopen(TASK ".inp", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> K;
for(int i = 1; i <= N; i++) cin >> a[i];
for(int i = 1; i <= N; i++) prefix[i] = prefix[i - 1] + a[i];
subtask::solution();
return (0 ^ 0);
}
