#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db long double
const ll inf = 1e18;
const int nx = 100005;
struct Line {
ll m, c;
Line(ll m = 0, ll c = -inf): m(m), c(c){};
};
int n, k;
ll a[nx], qs[nx];
ll dp[nx];
Line pv[nx];
int opt[nx][205];
deque<int> dq;
long double intersect(int x, int y) {
//if (pv[x].m == pv[x].m) return -inf;
return (db)(pv[x].c - pv[y].c) / (db)(pv[y].m - pv[x].m);
}
void reset() {
dq.clear();
dq.emplace_back(0);
}
void addLine(int z) {
while (dq.size() > 1) {
int x = dq[dq.size() - 2], y = dq.back();
if (pv[x].m == pv[y].m) {
if (pv[y].c > pv[x].c) {
dq.pop_back();
dq.pop_back();
dq.push_back(y);
} else {
dq.pop_back();
}
continue;
}
if (intersect(x, y) >= intersect(y, z)) {
dq.pop_back();
} else break;
}
//cout << "Add line: "<< pv[z].m << " " << pv[z].c << " " << z << endl;
dq.push_back(z);
}
pair<ll,int> query(ll val) {
while (dq.size() > 1) {
int x = dq.front(), y = dq[1];
if (pv[x].m == pv[y].m) {
if (pv[y].c < pv[x].c) {
dq.pop_front();
dq.pop_front();
dq.push_front(x);
} else {
dq.pop_front();
}
continue;
}
if (val >= intersect(x, y)) dq.pop_front();
else break;
}
int j = dq.front();
//cout << "Query: "<< pv[j].m << " " << pv[j].c << " " << j << " " << val << endl;
return make_pair(pv[j].m * val + pv[j].c, j);
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
qs[i] = qs[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
opt[i][0] = 0;
pv[i] = Line(qs[i], -qs[i] * qs[i]);
dp[i] = -inf;
}
ll ans = -1;
pv[0] = Line(0, 0);
for (int kk = 1; kk <= k; kk++) {
reset();
for (int i = 1; i <= n; i++) {
pair<ll,int> ans = query(qs[i]);
opt[i][kk] = ans.second;
dp[i] = ans.first;
addLine(i);
}
if (kk == k) ans = max(ans, dp[n]);
for (int i = 1; i <= n; i++) {
pv[i] = Line(qs[i], dp[i] - qs[i] * qs[i]);
//cout << dp[i] << " ";
dp[i] = -inf;
} cout << endl;
}
cout << ans << "\n";
int cur = n;
vector<int> cut;
for (int kk = k; kk >= 1; kk--) {
if (cur <= 0) break;
cut.push_back(opt[cur][kk]);
cur = opt[cur][kk];
}
for (int i = cut.size() - 1; i >= 0; i--) cout << cut[i] << " ";
}
/*
7 3
4 1 3 4 0 2 3
*/
