#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 1e5 + 5;
struct Line {
ll m, c;
Line(ll M, ll C) : m(M), c(C) { }
ll operator() (ll x) {
return m * x + c;
}
};
double intersect(Line a, Line b) {
if (a.m == b.m) {
if (a.c == b.c)
return (double)-1e9;
return (double)1e9;
}
return (double)(b.c - a.c) / (a.m - b.m);
}
deque<pair<pair<Line,double>,int>> lines;
void addLine(Line newLine, int x) {
while (lines.size() > 1 && lines.back().f.s >= intersect(lines.back().f.f, newLine))
lines.pop_back();
if (lines.empty())
lines.push_back({{newLine, 0.0}, x});
else
lines.push_back({{newLine, intersect(lines.back().f.f, newLine)}, x});
}
pair<ll,int> query(ll x) {
if (lines.size() == 0)
return {0, -1};
while (lines.size() > 1) {
if (lines[1].f.s <= (double)x)
lines.pop_front();
else
break;
}
return {lines[0].f.f(x), lines[0].s};
}
vector<ll> A;
ll dp[2][MAXN], pref[MAXN];
int opt[205][MAXN];
int main() {
fast
memset(opt, -1, sizeof(opt));
int n, k;
cin >> n >> k;
A = vector<ll>(n+1);
for (int i = 1; i <= n; i++) {
cin >> A[i];
pref[i] = pref[i-1] + A[i];
}
for (int i = 1; i <= n; i++) {
dp[0][i] = pref[i] * (pref[n] - pref[i]);
opt[1][i] = i;
}
for (int K = 2; K <= k; K++) {
int from = K % 2;
int to = 1 - K % 2;
lines.clear();
for (int i = 1; i <= n; i++) {
ll x = pref[i] - pref[n];
ll Q = query(x).f;
ll plc = query(x).s;
dp[to][i] = Q + pref[i] * (pref[n] - pref[i]);
opt[K][i] = plc;
addLine(Line(pref[i], dp[from][i]), i);
}
}
lines.clear();
for (int i = 1; i <= n-1; i++)
addLine(Line(pref[i], dp[1 - k%2][i]), i);
ll Q = query(0).f;
ll plc = query(0).s;
dp[k%2][n] = Q;
opt[k+1][n] = plc;
cout << dp[k%2][n] << "\n";
int now_k = k+1;
int now_plc = n;
while (now_k > 1) {
now_plc = opt[now_k][now_plc];
now_k--;
if (now_plc == -1)
cout << "1 ";
else
cout << now_plc << " ";
}
cout << "\n";
}
