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