#include <bits/stdc++.h>
#define MAXN 100100
#define MAXK 205
#define x real
#define y imag
using namespace std;
typedef long long int ll;
typedef complex<ll> point;
typedef pair<int, int> par;
ll dp[MAXN][MAXK], s[MAXN];
par _prev[MAXN][MAXK];
int n, k, arr[MAXN];
vector<point> hull, vecs;
vector<par> hull_ind;
ll cross(point va, point vb) {
return va.x() * vb.y() - va.y() * vb.x();
}
ll dot(point va, point vb) {
return va.x() * vb.x() + va.y() * vb.y();
}
void add_line(pair<point, par> npp) {
point np = npp.first;
while (!vecs.empty() && dot(vecs.back(), np - vecs.back()) > 0) {
vecs.pop_back();
hull.pop_back();
hull_ind.pop_back();
}
if (!hull.empty()) {
vecs.push_back(point(0, 1) * (np - hull.back()));
}
hull.push_back(np);
hull_ind.push_back(npp.second);
}
ll query(ll thex, int i1, int i2) {
point qp(thex, 1LL);
auto it = lower_bound(vecs.begin(), vecs.end(), qp, [](point a, point b) {
return cross(a, b) < 0;
});
_prev[i1][i2] = hull_ind[it-vecs.begin()];
return dot(qp, hull[it-vecs.begin()]);
}
bool comp(pair<point, par> aa, pair<point, par> bb) {
point a = aa.first, b = bb.first;
return a.x() < b.x();
}
void reset_hull() {
vecs.clear(), hull.clear(), hull_ind.clear();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for (int _i = 1; _i <= n; _i++)
cin >> arr[_i];
s[0] = 0;
for (int _i = 1; _i <= n; _i++)
s[_i] = arr[_i] + s[_i-1];
// dp[i][1] = s[i];
for (int _i = 1; _i <= n; _i++)
dp[_i][1] = s[_i];
vector<pair<point, par> > toadd;
for (int _i = 1; _i <= n; _i++)
add_line(make_pair(point(s[_i], - s[_i] * s[_i]), par(_i, 1)));
for (int j = 2; j <= k+1; j++) {
for (int _i = j; _i <= n; _i++) {
dp[_i][j] = query(s[_i], _i, j);
toadd.push_back(make_pair(point(s[_i], dp[_i][j] - s[_i] * s[_i]), par(_i, j)));
}
reset_hull();
sort(toadd.begin(), toadd.end(), comp);
for (int _i = 0; _i < toadd.size(); _i++)
add_line(toadd[_i]);
toadd.clear();
}
cout << dp[n][k+1] << "\n";
par p = _prev[n][k+1];
vector<int> indexes;
while (true) {
indexes.push_back(p.first);
if (p.second == 1)
break;
p = _prev[p.first][p.second];
}
for (int i = 0; i < indexes.size(); i++)
if (i < indexes.size() - 1)
cout << indexes[i] << " ";
else
cout << indexes[i] << "\n";
/*ll manual_ans = 0;
indexes.insert(indexes.begin(), n+1);
for (int i = 1; i < indexes.size(); i++) {
int ind = indexes[i];
int final = indexes[i-1];
// S[ind][final-1] * S[1][ind-1]
manual_ans += (s[final-1] - s[ind-1]) * s[ind-1];
cout << "I added S[" << ind << "][" << final-1 << "] * ";
cout << "S[" << 1 << "][" << ind-1 << "] to the ans \n";
}
cout << manual_ans << "\n";*/
}
