#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using i64 = long long;
const i64 inf = 1e17;
int par[1000005][201];
struct Line{
i64 m, c; int idx;
Line(i64 m = 0, i64 c = -inf, int idx = -1) : m(m), c(c), idx(idx) {}
i64 operator ()(i64 x){ return m * x + c; }
bool isOpt(const Line &ff, const Line &ss){
__int128 x = ff.c - c, y = ss.c - c;
x *= m - ss.m, y *= m - ff.m;
return x <= y;
}
};
signed main(){
int n, k; cin >> n >> k;
k += 1;
vector <i64> pf(n + 1);
for ( int i = 0; i < n; i++ ){
int x; cin >> x;
pf[i + 1] = pf[i] + x;
}
vector <deque<Line>> dq(k + 1);
for ( int i = 0; i <= k; i++ ) dq[i].pb(Line());
auto add = [&](auto &dq, int j, i64 dp){
Line cur = {pf[j], dp - pf[j] * pf[n], j};
while ( (int)dq.size() > 1 && dq[(int)dq.size() - 2].isOpt(cur, dq.back()) ){
dq.pop_back();
} dq.pb(cur);
};
auto qry = [&](auto &dq, i64 x){
while ( (int)dq.size() > 1 && dq[0](x) <= dq[1](x) ) dq.pop_front();
return pair <i64,int> {dq[0](x), dq[0].idx};
};
vector <i64> dp(k + 1, -inf);
dp[0] = 0;
add(dq[0], 0, 0);
for ( int i = 1; i <= n; i++ ){
vector <i64> nxt(k + 1, -inf);
for ( int j = 1; j <= k; j++ ){
auto [v, p] = qry(dq[j - 1], pf[i]);
v += (pf[n] - pf[i]) * pf[i];
nxt[j] = v; par[i][j] = p;
}
for ( int j = 1; j <= k; j++ ){
add(dq[j], i, nxt[j]);
}
swap(dp, nxt);
}
vector <int> p;
int j = n;
for ( int i = k; i > 1; i-- ){
p.pb(par[j][i]);
j = p.back();
}
cout << dp[k] << endl;
for ( int i = k - 2; i >= 0; i-- ){
cout << p[i] << ' ';
}
cout << '\n';
}
