#include <bits/stdc++.h>
using namespace std;
struct line {
long long c;
int m, id;
long long value(int x) {
return (long long) m * x + c;
}
line *left, *right;
line(int a, long long b, int d) : m(a), c(b), id(d), left(NULL), right(NULL) { };
};
struct mylichaotree {
line *root;
mylichaotree() {
root = new line(0, -1000000000, 0);
}
pair<long long, int> query(line *l_, int l, int r, int x) {
if (l_ == NULL) return {-1000000000, -1000000000};
if (l == r) return make_pair(l_->value(x), l_->id);
int mid = l + r >> 1;
if (x <= mid) return max(make_pair(l_->value(x), l_->id), query(l_->left, l, mid, x));
return max(make_pair(l_->value(x), l_->id), query(l_->right, mid + 1, r, x));
}
line* insert(line *l_, int l, int r, int m, long long c, int id) {
if (l_ == NULL || l == r) return new line(m, c, id);
int mid = l + r >> 1;
if ((long long) m * mid + c > l_->value(mid)) swap(m, l_->m), swap(c, l_->c), swap(id, l_->id);
if ((long long) m * l + c > l_->value(l)) l_->left = insert(l_->left, l, mid, m, c, id);
else l_->right = insert(l_->right, mid + 1, r, m, c, id);
return l_;
}
void insert(int a, long long b, int id) {
insert(root, 0, 1000000001, a, b, id);
}
pair<long long, int> query(int x) {
return query(root, 0, 1000000001, x);
}
} lct[201];
int par[201][100001], pre[100001];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
long long ans;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> pre[i], pre[i] += pre[i - 1];
vector<long long> to;
for (int i = 1; i <= n; i++) {
to.push_back(0);
for (int j = 1; j <= min(k, i - 1); j++) {
auto [x, y] = lct[j].query(pre[i]);
if (i == n && j == k) ans = x;
to.push_back(x);
par[j][i] = y;
}
for (int j = 1; j <= min(i, k); j++) lct[j].insert(pre[i], to[j - 1] - (long long) pre[i] * pre[i], i);
to.clear();
}
cout << ans << '\n';
for (int x = par[k][n], i = k; i >= 1; i--, x = par[i][x])
cout << x << ' ';
}
