#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define REP(i, b) for(int i = 0; i < b; i++)
#define PER(i, b) for(int i = b - 1; i >= 0; i--)
#define fi first
#define se second
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
using pii = pair < int, int >;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int K = 205;
struct CHT {
// Querying for max
struct Line {
ll a, b, id;
Line (ll _a = 0, ll _b = 0, ll _id = -1) { a = _a; b = _b; id = _id; };
ll cal(ll x) { return a * x + b; }
long double cross(Line o) { return (long double) (b - o.b) / (long double) (o.a - a); }
};
deque <Line> q;
/*
Decreasing slope;
add: >=
Increasing slope;
add: <=
*/
void add(ll a, ll b, ll id) {
Line nLine = Line(a, b, id);
while (q.size() >= 2 && q[0].cross(nLine) >= q[0].cross(q[1]))
q.pop_front();
q.push_front(nLine);
}
pair <ll, int> qry(ll x) {
int l = 0, r = (int) q.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (q[m].cal(x) < q[m + 1].cal(x))
l = m + 1;
else
r = m;
}
return {q[l].cal(x), q[l].id};
}
};
int n, k;
ll dp[2][N];
ll prf[N];
int opt[K][N];
// dp[i][k] = max j / (dp[j][k−1] + (pi − pj)⋅(pn − pi))
void run_case() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
int x; cin >> x;
prf[i] = prf[i - 1] + x;
}
// Base case, k = 0
for (int i = 1; i <= n; ++i) {
dp[0][i] = (prf[i] - prf[0]) * (prf[n] - prf[i]);
opt[1][i] = i;
}
for (int step = 1; step <= k; ++step) {
CHT hull;
hull.add(0, 0, 0);
for (int i = 1; i <= n; ++i) {
ll x = prf[n] - prf[i];
pair <ll, int> ret = hull.qry(x);
dp[1][i] = ret.fi + prf[i] * x;
opt[step][i] = ret.se;
hull.add(-prf[i], dp[0][i], i);
}
for (int i = 1; i <= n; ++i)
dp[0][i] = dp[1][i];
}
cout << dp[0][n] << "\n";
int i = opt[k][n];
vector <int> ids;
while (k) {
ids.push_back(i);
i = opt[k - 1][i];
--k;
}
reverse(ids.begin(), ids.end());
for (int x : ids) cout << x << " ";
cout << "\n";
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
#ifdef JASPER
freopen("in1", "r", stdin);
#endif
int Test = 1;
//cin >> Test;
for (int test = 1; test <= Test; test++){
run_case();
}
}
