/*
*/
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <random>
#include <queue>
#include <bitset>
// #define int long long
#define ll long long
#define ld long double
#define pb push_back
#define str string
using namespace std;
const int M = 998244353;
ll dp[100009];
int par[100009][209];
int zzz;
ld intersec(pair<pair<ll, ll>, int> w1, pair<pair<ll, ll>, int> w2) {
ld k1 = w1.first.first, b1 = w1.first.second;
ld k2 = w2.first.first, b2 = w2.first.second;
ld x = (b2 - b1) / (k1 - k2);
return x;
}
vector<pair<pair<ll, ll>, int>> s;
void add_line(ll k, ll b, int index) {
while (s.size() >= 2) {
ld x1 = intersec(s[s.size() - 2], s[s.size() - 1]);
ld x2 = intersec(s[s.size() - 2], {{k, b}, index});
if (x1 >= x2) {
s.pop_back();
} else {
break;
}
}
s.pb({{k, b}, index});
}
pair<ll, int> my_lower_bound(ll h) {
int left = zzz;
int right = (int) s.size();
int f = 0;
for (int mid = left + 1; mid < right; mid++) {
ld lol = intersec(s[mid - 1], s[mid]);
if (lol >= h) {
left = mid - 1;
f = 1;
break;
}
}
if (f == 0) left = s.size() - 1;
zzz = left;
return {h * s[left].first.first + s[left].first.second, s[left].second};
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k;
cin >> n >> k;
vector<ll> A(n + 1);
for (int i = 1; i <= n; i++) cin >> A[i];
vector<ll> pref = A;
for (int i = 1; i <= n; i++) pref[i] += pref[i - 1];
for (int i = 1; i <= n; i++) {
dp[i] = 0;
}
for (int t = 1; t <= k; t++) {
add_line(pref[t], dp[t] - pref[t] * pref[t], t);
zzz = 0;
for (int i = t + 1; i <= n; i++) {
pair<ll, int> kek = my_lower_bound(pref[i]);
add_line(pref[i], dp[i] - pref[i] * pref[i], i);
dp[i] = kek.first;
par[i][t] = kek.second;
}
s = {};
}
cout << dp[n] << '\n';
int i = n;
int t = k;
vector<ll> ans;
while (t >= 1) {
cout << par[i][t] << ' ';
i = par[i][t];
t--;
}
}
