#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
using pll = pair<int64_t, int64_t>;
#define x first
#define y second
const int64_t INF = 4e18;
int ccw(pll p0, pll p1, pll p2)
{
double cross = (double) (p1.x - p0.x) * (p2.y - p0.y) - (double) (p2.x - p0.x) * (p1.y - p0.y);
if (cross < -1e-5) return -1;
if (cross > 1e-5) return 1;
return 0;
}
int64_t calc(pll p, int64_t x) { return p.x * x + p.y; }
const int MAXN = 100007, MAXK = 207;
int trace[MAXK][MAXN];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int N, K;
cin >> N >> K;
vector<int64_t> S(N + 1, 0);
for (int i = 1; i <= N; ++i) cin >> S[i], S[i] += S[i - 1];
vector<int64_t> ans(N + 1, INF);
ans[0] = 0;
vector<pll> vec;
for (int t = 0; t <= K; ++t) {
int ptr = 0;
vec.clear();
for (int i = 0; i <= N; ++i) {
for (; ptr + 1 < (int) vec.size() && calc(vec[ptr], S[i]) > calc(vec[ptr + 1], S[i]); ++ptr);
int64_t newAns = (ptr >= (int) vec.size() ? INF : calc(vec[ptr], S[i]) + S[i] * S[i]);
if (ptr < ((int) vec.size())) trace[t][i] = vec[ptr].x / -2;
if (ans[i] != INF) {
pll cur(-2 * S[i], ans[i] + S[i] * S[i]);
while (((int) vec.size()) > 1 && ccw(cur, vec.rbegin()[0], vec.rbegin()[1]) <= 0) vec.pop_back();
vec.push_back(cur);
ptr = min(ptr, ((int) vec.size()) - 1);
}
ans[i] = newAns;
}
}
cout << (S[N] * S[N] - ans[N]) / 2 << endl;
for (int t = K, i = N; t > 0; --t) {
i = ((int) (upper_bound(S.begin(), S.begin() + i, trace[t][i]) - S.begin())) - 1;
cout << i << ' ';
}
cout << endl;
}
