#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(ll l1, ll l2, ll l3) {
return (B[l1] - B[l2]) * (A[l3] - A[l1]) <= (B[l3] - B[l1]) * (A[l1] - A[l2]);
}
void add(ll u, ll v, ll id) {
A.push_back(u);
B.push_back(v);
C.push_back(id);
while (A.size() >= 3 && bad(A.size() - 3, A.size() - 2, A.size() - 1)) {
A.erase(A.end() - 2);
B.erase(B.end() - 2);
C.erase(C.end() - 2);
}
}
ll cal(pii u, ll x) {
return u.fi * x + u.se;
}
ll ptr = 0;
pii get(ll x) {
if (ptr >= A.size()) {
ptr = A.size() - 1;
return {cal({A[ptr], B[ptr]}, x), C[ptr]};
}
while (ptr < A.size() - 1 && cal({A[ptr], B[ptr]}, x) <= cal({A[ptr + 1], B[ptr + 1]}, x)) {
//cout << cal({A[ptr], B[ptr]}, x) << " " << cal({A[ptr + 1], B[ptr + 1]}, x) << endl;
ptr ++ ;
}
//cout << endl;
return {cal({A[ptr], B[ptr]}, x), C[ptr]};
}
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();
ptr = 0;
for (int i = n; i >= 1; i--) {
if (i > n) {
f[i][z % 2] = -inf;
continue;
}
if (z == 0) {
f[i][z % 2] = 0;
continue;
}
if (z > 0 && 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;
}
}
}
cout << f[1][k % 2] << endl;
ll cur = 1, curk = k;
while (true) {
cur = where[cur][curk] + 1;
cout << cur - 1 << " ";
curk -- ;
if (curk <= 0) break;
}
return 0;
}
