#include <bits/stdc++.h>
typedef long long ll;
#define fi first
#define se second
#define pii pair<ll,ll>
#define endl '\n'
#define N 100005
#define inf 1e18
using namespace std;
int n, k, a[N], where[N][202];
ll f[N][2], pf[N];
vector<ll> A, B, C;
bool bad(int l1, int l2, int l3) {
return (B[l1] - B[l2]) * (A[l3] - A[l1]) <= (B[l3] - B[l1]) * (A[l1] - A[l2]);
}
deque<int> dq;
ll cal(int id, ll x) {
return A[id] * x + B[id];
}
// pf[i]
// -pf[i] * pf[i] + pf[n] * pf[i] + f[i + 1][1 - (z % 2)]
void add(ll u, ll v, ll idx) {
A.push_back(u);
B.push_back(v);
C.push_back(idx);
ll id = A.size() - 1;
while (dq.size() >= 2 && bad(dq[dq.size() - 2], dq[dq.size() - 1], id)) {
dq.pop_back();
}
dq.push_back(id); // ta khong can pop tai A, B, C, vi dq luu chi so, va gio chi can luu nhu vay
}
pii get(ll x) {
while (dq.size() >= 2 && cal(dq[0], x) < cal(dq[1], x)) {
dq.pop_front();
}
return {cal(dq[0], x), C[dq[0]]};
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pf[i] = pf[i - 1] + a[i];
}
for (int z = 0; z <= k; z++) {
A.clear();
B.clear();
C.clear();
dq.clear();
for (int i = n; i >= 1; i--) {
if (z == 0) {
f[i][z % 2] = 0;
continue;
}
if (i < n) {
add(pf[i], -pf[i] * pf[i] + pf[n] * pf[i] + f[i + 1][1 - (z % 2)], i);
}
if (i < n) {
pii xet = get(pf[i - 1]);
f[i][z % 2] = xet.fi - pf[n] * pf[i - 1];
where[i][z] = xet.se;
}
else {
f[i][z % 2] = -inf;
}
}
}
cout << f[1][k % 2] << endl;
ll cur = 1, curk = k;
while (curk > 0) {
cur = where[cur][curk] + 1;
cout << cur - 1 << " ";
curk--;
}
return 0;
}
