#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn = 100005;
const int mxk = 205;
const ll INF = 2e18; // Use a very large sentinel
struct line {
int m; // Slope is p[i] <= 10^9, fits in int
ll b; // Intercept fits in ll
int id; // Index fits in int
ll eval(ll x) const {
if (id == -1) return -INF;
return 1ll * m * x + b;
}
};
struct node {
int lc, rc;
line li;
} tn[mxn * 32]; // With compression, 32*N nodes is plenty
int node_cnt = 0;
ll coords[mxn];
int num_coords = 0;
int create() {
node_cnt++;
tn[node_cnt].lc = tn[node_cnt].rc = -1;
tn[node_cnt].li = {0, -INF, -1};
return node_cnt;
}
void upd(line new_l, int v, int l, int r) {
int mid = l + (r - l) / 2;
bool mid_better = new_l.eval(coords[mid]) > tn[v].li.eval(coords[mid]);
if (mid_better) swap(new_l, tn[v].li);
if (l == r) return;
if (new_l.eval(coords[l]) > tn[v].li.eval(coords[l])) {
if (tn[v].lc == -1) tn[v].lc = create();
upd(new_l, tn[v].lc, l, mid);
} else if (new_l.eval(coords[r]) > tn[v].li.eval(coords[r])) {
if (tn[v].rc == -1) tn[v].rc = create();
upd(new_l, tn[v].rc, mid + 1, r);
}
}
pair<ll, int> qry(int x_rank, int v, int l, int r) {
if (v == -1 || tn[v].li.id == -1) return {-INF, -1};
ll x_val = coords[x_rank];
pair<ll, int> res = {tn[v].li.eval(x_val), tn[v].li.id};
if (l == r) return res;
int mid = l + (r - l) / 2;
if (x_rank <= mid) res = max(res, qry(x_rank, tn[v].lc, l, mid));
else res = max(res, qry(x_rank, tn[v].rc, mid + 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;
if (!(cin >> n >> k)) return 0;
vector<ll> temp_p;
for (int i = 1; i <= n; i++) {
ll 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++) {
node_cnt = 0;
int root = create();
int cur = j % 2, prev = (j - 1) % 2;
for (int i = 1; i <= n; i++) {
// 1. Query first
if (i > j) {
auto res = qry(get_rank(p[i]), root, 1, num_coords);
dp[cur][i] = res.first;
pr[j][i] = res.second;
} else {
dp[cur][i] = -1;
}
// 2. Add line for valid split points
if (i >= j && i < n && dp[prev][i] != -1) {
upd({(int)p[i], dp[prev][i] - 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 ? "" : " ");
}
return 0;
}
