#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define ll long long int
#define ld long double
const int N = 1e5 + 10;
const int md = 1e9 + 7;
// const int INF = 1e18;
struct node {
ll k, b;
int ind;
};
struct CHT {
deque<node> hull;
ll f(pair<ll, ll> line, ll x) {
return line.first * x + line.second;
}
int lefff = 0;
pair<ll, int> get(int x, int ind) {
while ((lefff + 1) < (int) hull.size() && f({hull[lefff].k, hull[lefff].b}, x) <= f({hull[lefff + 1].k, hull[lefff + 1].b}, x) && hull[lefff + 1].ind < ind) {
lefff++;
}
return {f({hull[lefff].k, hull[lefff].b}, x), hull[lefff].ind};
}
ld intersect(ll k1, ll b1, ll k2, ll b2) {
return (ld)(b2 - b1) / (ld)(k1 - k2);
}
ld intersect(pair<ll, ll> line1, pair<ll, ll> line2) {
return intersect(line1.first, line1.second, line2.first, line2.second);
}
void add(ll k, ll b, int ind) {
pair<ll, ll> line = pair<ll, ll> (k, b);
while (hull.size() > 1) {
int s = (int) hull.size();
if (intersect({hull[s - 2].k, hull[s - 2].b}, line) <= intersect({hull[s - 2].k, hull[s - 2].b}, {hull[s - 1].k, hull[s - 1].b})) {
hull.pop_back();
}
else break;
}
hull.push_back({k, b, ind});
}
};
int dp[N][205];
int32_t main(int32_t argc, char *argv[]) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
int n, k;
cin >> n >> k; k++;
vector<int> a(n + 1);
vector<ll> pref(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
CHT hull, hull1, hull2;
// vector<vector<pair<int, int>>> dp(n + 1, vector<pair<int, int>> (k + 1));
ll res = 0;
for (int j = 1; j <= k; j++) {
if (j != 1) {
for (int i = j; i <= n; i++) {
auto xy = hull.get(pref[i], i);
dp[i][j] = xy.second;
// cout << i << " " << j << " " << xy.first << '\n';
hull1.add(pref[i], -pref[i] * pref[i] + xy.first, i);
if (i == n && j == k)
res = xy.first;
}
hull = hull1;
hull1 = hull2;
// cout << '\n';
} else
for (int i = 1; i <= n; i++) {
hull.add(pref[i], -pref[i] * pref[i], i);
}
}
cout << res << '\n';
int i = n, j = k;
vector<int> ans;
while (j != 1) {
i = dp[i][j]; j--;
ans.push_back(i);
}
reverse(ans.begin(), ans.end());
for (auto i: ans)
cout << i << " ";
cout << '\n';
}
return 0;
}
