#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 ll INF = 1e18;
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int K = 205;
// Query for min;
struct ConvexHull {
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;
void add(ll a, ll b, ll id) {
Line nLine = Line(a, b, id);
// need to change when a is increasing or decreasing
while (q.size() >= 2
&& (q.back().cross(nLine) <= q.back().cross(q[q.size() - 2])
|| (q.back().a == nLine.a && q.back().b <= nLine.b)))
q.pop_back();
q.push_back(nLine);
}
pair <ll, int> qry(ll x) {
while (q.size() >= 2 && q[0].cal(x) <= q[1].cal(x))
q.pop_front();
return {q[0].cal(x), q[0].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 step = 1; step <= k + 1; ++step) {
ConvexHull hull;
hull.add(0, 0, -1);
for (int i = 1; i <= n; ++i) {
pair <ll, int> ret = hull.qry(prf[i]);
dp[1][i] = ret.fi + prf[i] * (prf[n] - prf[i]);
opt[step][i] = ret.se;
if (step != 1)
hull.add(prf[i], dp[0][i] - prf[i] * prf[n], i);
}
for (int i = 1; i <= n; ++i)
dp[0][i] = dp[1][i];
}
cout << dp[0][n] << "\n";
vector <int> ids;
for (int i = k + 1, id = n; i > 0; --i) {
if (id != n)
ids.push_back(id);
id = opt[i][id];
}
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();
}
}
