#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int N_MAX = 1e5;
struct defLine {
int64 slope, h; int index;
int64 getEval (int64 t) {return slope * t + h;}
long double intersectX (defLine aux) {return (long double)(aux.h - h) / (slope - aux.slope);}
bool getIn (defLine first, defLine second) {return first.intersectX ({slope, h}) <= first.intersectX (second);}
};
deque<defLine> CHT;
void push (defLine newLine) {
while (CHT.size () >= 2 && newLine.getIn (CHT[CHT.size () - 2], CHT[CHT.size () - 1]))
CHT.pop_back ();
CHT.push_back (newLine);
}
const int NONE = -1;
const int64 INF = 1e18;
defLine query (int64 target) {
if (CHT.size () == 0)
return {0, -INF, NONE};
while (CHT.size () >= 2 && CHT[0].getEval (target) <= CHT[1].getEval (target))
CHT.pop_front ();
return CHT[0];
}
int n, k; int64 input[1 + N_MAX], pSum[1 + N_MAX];
void initInput (void) {
cin >> n >> k;
for (int i = 1; i <= n; i ++)
cin >> input[i];
for (int i = 1; i <= n; i ++)
pSum[i] = pSum[i - 1] + input[i];
}
const int K_MAX = 200;
int pointTo[1 + K_MAX][1 + N_MAX];
int64 DP[1 + N_MAX], prevDP[1 + N_MAX];
void solve (void) {
for (int t = 1; t <= k; t ++) {
for (int i = 1; i <= t; i ++) {
DP[i] = -INF;
defLine line = {pSum[i], prevDP[i] - pSum[i] * pSum[i], i};
push (line);
}
for (int i = t + 1; i <= n; i ++) {
defLine bestLine = query (pSum[i]);
pointTo[t][i] = bestLine.index;
DP[i] = bestLine.getEval (pSum[i]);
///if (t == 1 && i == 3)
/// cout << DP[i] << "\n";
defLine newLine = {pSum[i], prevDP[i] - pSum[i] * pSum[i], i};
push (newLine);
}
CHT.clear ();
for (int i = 1; i <= n; i ++)
prevDP[i] = DP[i];
}
cout << DP[n] << "\n";
int t = k, p = n;
while (t > 0) {
cout << pointTo[t][p] << " ";
p = pointTo[t][p], t --;
}
}
int main()
{
initInput ();
solve ();
return 0;
}
