#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef tuple<ll, ll, double, ll> t;
int N, K;
vector<int> psum;
double intersect(t L1, t L2) {
return (get<1>(L2)-get<1>(L1))/(get<0>(L1)-get<0>(L2));
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> K; psum.resize(N);
for (auto &i: psum) cin >> i;
for (int i=1; i<N; i++) psum[i] = psum[i-1] + psum[i];
int prev[K][N];
ll DP[2][N];
t g;
fill(&prev[0][0], &prev[K-1][N], 0);
fill(&DP[0][0], &DP[1][N], 0);
for (int k=0; k<K; k++) {
deque<t> F; F.push_front(t(0, -1e14, -1, -1));
for (int i=k+1; i<N; i++) {
g = t(psum[i-1], DP[(k%2)^1][i-1]-psum[i-1]*psum[i-1], 0, i-1);
if (get<0>(F.back()) == get<0>(g) && get<1>(F.back()) < get<1>(g)) {
F.pop_back();
while (!F.empty()) {
g = t(get<0>(g), get<1>(g), intersect(F.back(), g), get<3>(g));
if (get<2>(F.back()) < get<2>(g)) break;
F.pop_back();
}
F.push_back(g);
}
else if (get<0>(F.back()) != get<0>(g)) {
while (!F.empty()) {
g = t(get<0>(g), get<1>(g), intersect(F.back(), g), get<3>(g));
if (get<2>(F.back()) < get<2>(g)) break;
F.pop_back();
}
F.push_back(g);
}
ll X = psum[i];
while (F.size() > 1 && get<2>(F.at(1)) < X) F.pop_front();
DP[k%2][i] = get<0>(F.front()) * X + get<1>(F.front());
prev[k][i] = get<3>(F.front());
}
}
cout << DP[(K-1)%2][N-1] << '\n';
int temp = N-1, q = K-1;
vector<int> L;
while (q>=0) {
L.push_back(prev[q][temp]+1);
temp = prev[q--][temp];
}
sort(L.begin(), L.end());
for (auto &i: L) cout << i << ' ';
}
