#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vint = vector<int>;
using vll = vector<ll>;
using pint = pair<int, int>;
using vpint = vector<pint>;
using plli = pair<ll, int>;
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a)-1; i >= (b); i--)
#define fi first
#define se second
const ll INF = 5e18;
struct Line {
int i;
ll m, c;
ll eval(ll x) { return m*x + c; }
};
struct LiChao {
int n;
vector<Line> tree;
vll& coords;
vint modified;
const Line null_line = {-1, 0, -INF};
LiChao(vll& coords): n(sz(coords)), tree(4*n, null_line), coords(coords) {
modified.reserve(4*n);
}
void clear() {
for (auto& i: modified) tree[i] = null_line;
modified.clear();
}
void update(int v, int tl, int tr, Line n_line) {
int tm = tl + (tr - tl)/2;
bool mid_better = n_line.eval(coords[tm]) >= tree[v].eval(coords[tm]);
bool left_better = n_line.eval(coords[tl]) >= tree[v].eval(coords[tl]);
if (mid_better) swap(tree[v], n_line);
if (tl == tr) return;
if (left_better != mid_better) update(2*v, tl, tm, n_line);
else update(2*v+1, tm+1, tr, n_line);
}
plli query(int v, int tl, int tr, int pos) {
ll val = tree[v].eval(coords[pos]);
int i = tree[v].i;
if (tl == tr) return {val, i};
int tm = tl + (tr - tl)/2;
plli res;
if (pos <= tm) res = query(2*v, tl, tm, pos);
else res = query(2*v+1, tm+1, tr, pos);
if (res.fi > val) return res;
return {val, i};
}
};
void solve() {
int n, k; cin >> n >> k;
vint a(n); rep(i, n) cin >> a[i];
vint prefix(n);
rep(i, n) prefix[i] = i == 0 ? a[i] : a[i] + prefix[i-1];
vint suffix(n);
rrep(i, n) suffix[i] = i == n-1 ? 0 : a[i+1] + suffix[i+1];
vll coords(all(suffix)); sort(all(coords)); coords.erase(unique(all(coords)), coords.end());
auto get_pos = [&](ll x) {
return lower_bound(all(coords), x) - coords.begin();
};
vector<ll> p_dp(n-1, -INF), c_dp(n-1, -INF);
vector<vint> dp_i(k, vint(n-1));
LiChao lc(coords);
rep(l, k) {
if (l == 0) rep(i, n-1) c_dp[i] = (ll)prefix[i]*suffix[i];
else {
lc.clear();
rep(i, n-1) {
if (i > 0 && p_dp[i-1] != -INF) {
Line n_line = {i-1, -prefix[i-1], p_dp[i-1]};
lc.update(1, 0, lc.n-1, n_line);
}
int pos = get_pos(suffix[i]);
auto res = lc.query(1, 0, lc.n-1, pos);
if (res.se != -1) {
c_dp[i] = (ll)prefix[i]*suffix[i] + res.first;
dp_i[l][i] = res.se;
}
}
}
p_dp = c_dp;
c_dp.assign(n-1, -INF);
}
ll res = -INF, res_i = -1;
FOR(i, k-1, n-1) if (res < p_dp[i]) res = p_dp[i], res_i = i;
cout << res << endl;
vint pos(k);
rrep(i, k)
pos[i] = res_i, res_i = dp_i[i][res_i];
rep(i, k) cout << pos[i]+1 << " ";
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
