#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct line {
int idx;
ll a, b;
line(int idx, ll a, ll b) : idx(idx), a(a), b(b) {}
ll cost(ll x) const {
return a * (x - a) + b;
}
ll intersect(line const& other) {
if (a == other.a) return 1LL << 32;
return ((other.a * other.a - other.b) - (a * a - b)) / (other.a - a);
}
};
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<ll> pref(n + 1, 0);
partial_sum(a.begin(), a.end(), pref.begin() + 1);
vector<ll> dp1(n + 1, 0);
int parent[k + 1][n + 1];
for (int i = 1; i <= k; ++i) {
vector<ll> dp2(n + 1, 0);
deque<line> dq;
for (int j = 0; j <= n; ++j) {
while (dq.size() > 1 &&
dq[0].cost(pref[j]) <= dq[1].cost(pref[j])) {
dq.pop_front();
}
if (!dq.empty()) {
dp2[j] = dq[0].cost(pref[j]);
parent[i][j] = dq[0].idx;
}
line l(j, pref[j], dp1[j]);
while (dq.size() > 1) {
int sz = dq.size();
ll t1 = dq[sz - 2].intersect(dq[sz - 1]);
ll t2 = dq[sz - 1].intersect(l);
if (t1 < t2) break;
dq.pop_back();
}
dq.push_back(l);
}
dp1 = move(dp2);
}
cout << dp1[n] << endl;
int u = n;
for (int i = k; i > 0; --i) {
u = parent[i][u];
cout << u << ' ';
}
cout << endl;
return 0;
}
