#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
struct Line{
int m, c, idx;
Line(int m = 0, int c = 0, int idx = 0) : m(m), c(c), idx(idx) {}
int operator ()(int x){ return m * x + c; }
long double operator ^(const Line &t){
return (c - t.c + .0) / (t.m - m);
}
bool isOpt(Line ff, Line ss){
__int128 p = c - ff.c, q = c - ss.c;
p *= ss.m - m, q *= ff.m - m;
return p <= q;
};
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
vector <int> a(n), pf(n + 1);
for ( auto &u: a ){
cin >> u;
}
for ( int i = 0; i < n; i++ ){
pf[i + 1] = pf[i] + a[i];
}
vector <vector<int>> fa(n + 1, vector <int> (k + 1));
vector <int> dp(n + 1);
for ( int j = 1; j <= k; j++ ){
auto nxt = dp;
deque <Line> dq;
auto ins = [&](int j){
Line nw = {pf[j], dp[j] - pf[j] * pf[j], j};
while ( dq.size() > 1 && dq[(int)dq.size() - 2].isOpt(nw, dq.back()) ){
dq.pop_back();
}
dq.pb(nw);
};
ins(0);
for ( int i = 1; i <= n; i++ ){
while ( dq.size() > 1 && dq[0](pf[i]) <= dq[1](pf[i]) ){
dq.pop_front();
}
nxt[i] = dq[0](pf[i]);
fa[i][j] = dq[0].idx;
ins(i);
}
swap(dp, nxt);
}
vector <int> ans;
int x = n;
for ( int i = k; i > 0; i-- ){
ans.pb(fa[x][i]);
x = fa[x][i];
}
reverse(all(ans));
cout << dp.back() << ln;
for ( auto &u: ans ){
cout << u << ' ';
}
cout << '\n';
}
/*
7 3
4 1 3 4 0 2 3
*/
