#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (1e5)+1, K = 201;
struct MaxHull {
struct line {
ll m, c;
int i;
ll getVal(ll x) { return m*x + c; };
};
int idx = 0;
vector<line> lines;
bool bad(line l1, line l2, line l3) {
assert(l1.m <= l2.m && l2.m <= l3.m);
return (double) (l3.c-l1.c)*(l1.m-l2.m) <= (double) (l2.c-l1.c)*(l1.m-l3.m);
}
void update(ll m, ll c, int i) {
line l = {m, c, i};
while(lines.size() > 3 && bad(lines[lines.size()-2], lines[lines.size()-1], l)) lines.pop_back();
lines.push_back(l);
}
pair<ll, int> query(ll x) {
assert(!lines.empty());
while(idx+1 < lines.size() && lines[idx+1].getVal(x) > lines[idx].getVal(x)) ++idx;
return make_pair(lines[idx].getVal(x), lines[idx].i);
}
} hull;
int n, k, a[N], trace[K][N];
ll ans, s[N], dp[N];
vector<int> order;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i-1] + a[i];
hull.update(s[i], -s[i]*s[i], i);
}
for(int cnt = 1; cnt <= k; cnt++) {
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++) tie(dp[i], trace[cnt][i]) = hull.query(s[i]);
hull.idx = 0;
hull.lines.clear();
for(int i = cnt+1; i <= n; i++) hull.update(s[i], dp[i] - s[i]*s[i], i);
}
for(int cnt = k, i = n; cnt >= 1; i = trace[cnt][i], cnt--) order.push_back(trace[cnt][i]);
reverse(order.begin(), order.end());
cout << dp[n] << endl;
for(int i: order) cout << i << ' ';
}
