#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn = 100005;
const int mxk = 205;
ll p[mxn];
ll dp[2][mxn];
int pr[mxk][mxn];
struct Line {
ll m, b;
int id;
ll eval(ll x) { return m * x + b; }
};
// Intersection check using __int128 to prevent overflow
// Checks if l2 is redundant because of l1 and l3
bool is_bad(Line l1, Line l2, Line l3) {
// (b1-b2)/(m2-m1) >= (b2-b3)/(m3-m2)
return (__int128)(l1.b - l2.b) * (l3.m - l2.m) >= (__int128)(l2.b - l3.b) * (l2.m - l1.m);
}
Line q[mxn];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k;
if (!(cin >> n >> k)) return 0;
for (int i = 1; i <= n; i++) {
ll x; cin >> x;
p[i] = p[i - 1] + x;
}
for (int j = 1; j <= k; j++) {
int head = 0, tail = 0;
int cur = j % 2;
int prev = (j - 1) % 2;
// Note: For j splits, we only care about split points from index j-1 to n-1
for (int i = 1; i <= n; i++) {
// 1. Query: Find the best line for x = p[i]
// Since p[i] is non-decreasing, we just pop from the front
if (i > j) {
while (tail - head >= 2 && q[head].eval(p[i]) <= q[head + 1].eval(p[i])) {
head++;
}
dp[cur][i] = q[head].eval(p[i]);
pr[j][i] = q[head].id;
} else {
dp[cur][i] = 0;
}
// 2. Add: Current index i as a split point candidate for the NEXT part
// Slope m = p[i], Intercept b = dp[prev][i] - p[i]^2
if (i >= j && i < n) {
Line now = {p[i], dp[prev][i] - p[i] * p[i], i};
// Handle duplicate slopes (p[i] stays same if a[i] is 0)
if (tail > head && q[tail - 1].m == now.m) {
if (now.b >= q[tail - 1].b) tail--;
else continue;
}
while (tail - head >= 2 && is_bad(q[tail - 2], q[tail - 1], now)) {
tail--;
}
q[tail++] = now;
}
}
}
cout << dp[k % 2][n] << "\n";
// Backtracking
int curr_n = n;
for (int j = k; j >= 1; j--) {
curr_n = pr[j][curr_n];
cout << curr_n << (j == 1 ? "" : " ");
}
cout << endl;
return 0;
}
