#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 {
const Line null_line = {-1, 0, -INF};
int n;
vector<Line> tree;
vll& coords;
vint modified;
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(Line n_line) {
int v = 1, tl = 0, tr = n-1;
while (tl <= tr) {
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) {
if (tree[v].i == -1) modified.push_back(v);
swap(tree[v], n_line);
}
if (tl == tr) break;
if (left_better != mid_better) v = 2*v, tr = tm;
else v = 2*v+1, tl = tm+1;
}
}
plli query(int pos) {
int v = 1, tl = 0, tr = n-1;
ll x_val = coords[pos];
ll best_val = -INF;
int best_i = -1;
while (tl <= tr) {
ll val = tree[v].eval(x_val);
int i = tree[v].i;
if (val > best_val) best_val = val, best_i = i;
if (tl == tr) break;
int tm = tl + (tr - tl)/2;
if (pos <= tm) v = 2*v, tr = tm;
else v = 2*v+1, tl = tm+1;
}
return {best_val, best_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());
vint suffix_pos(n); rep(i, n) suffix_pos[i] = lower_bound(all(coords), suffix[i]) - 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(n_line);
}
int pos = suffix_pos[i];
auto res = lc.query(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;
}
