#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e12 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
const int MAX_N = 1e5 + 10, MAX_K = 210;
ll hist[MAX_N][MAX_K];
ll pref[MAX_N], arr[MAX_N];
struct Line {
ll a, b, ind;
long double p;
Line() {}
Line(ll _a, ll _b, ll _ind) {a = _a; b = _b; ind = _ind;}
ll y(ll x) {return a * x + b;}
long double getWhere(const Line &other) {
if(a == other.a) {
return -mod;
} else {
return (long double)(b - other.b) / (long double)(other.a - a);
}
}
};
struct LineContainer {
deque<Line> lines;
void addLine(Line curr) {
while(!lines.empty() && lines.back().getWhere(curr) <= lines.back().p) {
lines.pop_back();
}
if(lines.empty()) {
curr.p = -mod;
} else {
curr.p = lines.back().getWhere(curr);
}
lines.push_back(curr);
}
pair<ll, int> get(ll x) {
while(lines.size() > 1 && lines[1].p <= x) {
lines.pop_front();
}
return {lines.front().y(x), lines.front().ind};
}
};
LineContainer lc[MAX_K];
void output(int n, int k) {
if(k == 0) {
return;
}
output(hist[n][k], k - 1);
cout << hist[n][k] << " ";
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i ++) {
cin >> arr[i];
pref[i] = pref[i - 1] + arr[i];
}
for(int i = 1; i <= k; i ++) {
lc[i].addLine(Line(0, -mod, -1));
}
lc[0].addLine(Line(0, 0, -1));
ll ret;
for(int i = 1; i <= n; i ++) {
for(int j = k; j >= 1; j --) {
auto get = lc[j - 1].get(pref[i]);
hist[i][j] = get.second;
if(i == n && j == k) {ret = get.first;}
lc[j].addLine(Line(pref[i], get.first - pref[i] * pref[i], i));
}
lc[0].addLine(Line(pref[i], 0 - pref[i] * pref[i], i));
}
cout << ret << endl;
output(n, k);
return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/
