#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct State { long long L, R, px, py; };
bool operator<(const State &a1, const State &a2) {
if (a1.L < a2.L) return true;
return false;
}
class ConvexHullTrick {
public:
vector<State>S;
long long merge(long long vx, long long vy, long long wx, long long wy) {
long long F = wy + (wx - vx)*(wx - vx) - vy;
long long G = F / (2LL * (wx - vx));
return G;
}
void add(long long vx, long long vy) {
long long LL = -(1LL << 60);
while (!S.empty()) {
State G = S[S.size() - 1];
if (G.px == vx) {
if (G.py > vy) {
S.pop_back();
}
else {
return;
}
}
else {
long long D = merge(G.px, G.py, vx, vy);
if (G.L > D) {
S.pop_back();
}
else {
S[S.size() - 1].R = D;
S.push_back(State{ D + 1,(1LL << 60),vx,vy });
return;
}
}
}
S.push_back(State{ LL, (1LL << 60),vx,vy });
}
pair<long long, long long> mincost(long long pos) {
int pos1 = lower_bound(S.begin(), S.end(), State{ pos, (1LL << 60), 0LL, 0LL }) - S.begin(); pos1--;
State G = S[pos1];
return make_pair(G.py + (pos - G.px)*(pos - G.px), G.px);
}
};
long long N, K, A[100009], S; pair<long long, long long>dp[10009][209];
int main() {
cin >> N >> K; K++;
for (int i = 1; i <= N; i++) { cin >> A[i]; S += A[i]; }
for (int i = 1; i <= N; i++) A[i] += A[i - 1];
for (int i = 0; i <= N; i++) { for (int j = 0; j <= K; j++) dp[i][j] = make_pair((1LL << 60), -1); }
dp[0][0] = make_pair(0, -1);
for (int j = 1; j <= K; j++) {
ConvexHullTrick X;
for (int i = 1; i <= N; i++) {
X.add(A[i - 1], dp[i - 1][j - 1].first);
pair<long long, long long>T = X.mincost(A[i]);
dp[i][j].first = T.first;
int pos1 = lower_bound(A, A + N + 1, T.second) - A;
dp[i][j].second = pos1;
}
}
vector<int>C; int cx = N, cy = K;
while (cx >= 1) {
if (cx != N) C.push_back(cx);
cx = dp[cx][cy].second; cy--;
}
reverse(C.begin(), C.end());
cout << (S*S - dp[N][K].first) / 2 << endl;
for (int i = 0; i < C.size(); i++) {
if (i)cout << " "; cout << C[i];
}
cout << endl;
return 0;
}
