#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn = 100005;
const int mxk = 205;
struct line {
ll m = 0, b = -2e18; // Use very small b for empty lines
int idx = -1;
ll eval(ll x) { return m * x + b; }
};
struct node {
int lc = -1, rc = -1;
line li;
} tn[mxn * 40]; // 40 * N is safe for Li-Chao with compression
int cnt = 0;
ll coords[mxn]; // Sorted unique values of p[i]
int num_coords = 0;
int create() {
cnt++;
tn[cnt].lc = -1;
tn[cnt].rc = -1;
tn[cnt].li = line();
return cnt;
}
// upd and qry now work on rank indices [1, num_coords]
void upd(line li, int i, int l, int r) {
int m = l + (r - l) / 2;
// Eval using the actual value at the rank index m
bool mid_better = li.eval(coords[m]) > tn[i].li.eval(coords[m]);
if (mid_better) swap(li, tn[i].li);
if (l == r) return;
if (li.eval(coords[l]) > tn[i].li.eval(coords[l])) {
if (tn[i].lc == -1) tn[i].lc = create();
upd(li, tn[i].lc, l, m);
} else if (li.eval(coords[r]) > tn[i].li.eval(coords[r])) {
if (tn[i].rc == -1) tn[i].rc = create();
upd(li, tn[i].rc, m + 1, r);
}
}
pair<ll, int> qry(int x_rank, int i, int l, int r) {
if (i == -1) return {-2e18, -1};
ll x_val = coords[x_rank];
pair<ll, int> res = {tn[i].li.eval(x_val), tn[i].li.idx};
if (l == r) return res;
int m = l + (r - l) / 2;
if (x_rank <= m) res = max(res, qry(x_rank, tn[i].lc, l, m));
else res = max(res, qry(x_rank, tn[i].rc, m + 1, r));
return res;
}
ll p[mxn];
ll dp[2][mxn];
int pr[mxk][mxn];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k;
cin >> n >> k;
vector<ll> temp_p;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
p[i] = p[i - 1] + x;
temp_p.push_back(p[i]);
}
// Coordinate Compression
sort(temp_p.begin(), temp_p.end());
temp_p.erase(unique(temp_p.begin(), temp_p.end()), temp_p.end());
num_coords = temp_p.size();
for (int i = 0; i < num_coords; i++) coords[i + 1] = temp_p[i];
auto get_rank = [&](ll val) {
return lower_bound(coords + 1, coords + num_coords + 1, val) - coords;
};
for (int j = 1; j <= k; j++) {
cnt = 0;
int root = create();
int cur = j % 2;
int prev = (j - 1) % 2;
for (int i = 1; i <= n; i++) {
// 1. Query for the best previous split
if (i > j) {
auto q = qry(get_rank(p[i]), root, 1, num_coords);
dp[cur][i] = q.first;
pr[j][i] = q.second;
} else {
dp[cur][i] = 0;
}
// 2. Add line from previous layer: slope p[i], intercept dp[prev][i] - p[i]^2
// We use i < n because we can't split after the very last element
if (i < n) {
upd({p[i], dp[prev][i] - 1ll * p[i] * p[i], i}, root, 1, num_coords);
}
}
}
cout << dp[k % 2][n] << "\n";
int curr_n = n;
for (int j = k; j >= 1; j--) {
curr_n = pr[j][curr_n];
cout << curr_n << (j == 1 ? "" : " ");
}
cout << endl;
return 0;
}
