#include <bits/stdc++.h>
#define MAXN 100005
#define MAXK 205
#define OO -1000000000000000000LL
using namespace std;
typedef long long int ll;
vector<ll> dpprev, dpnow;
int n, k, arr[MAXN], s[MAXN], dprev[MAXN], layer;
void DCT(int a, int b, int op1, int op2) {
if (a > b) return;
int mid = (a + b) / 2;
int theop = op1;
for (int op = max(layer-1, op1); op <= min(min(op2, n), mid-1); op++)
if (dpnow[mid-1] < dpprev[op-1] + s[op] * (s[mid] - s[op]))
theop = op,
dpnow[mid-1] = dpprev[op-1] + s[op] * (s[mid] - s[op]),
dprev[mid] = theop;
DCT(a, mid-1, op1, theop), DCT(mid+1, b, theop, op2);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
memset(dprev, -1, sizeof(dprev));
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] = s[i-1] + arr[i];
for (int i = 1; i <= n; i++)
dpprev.push_back(0);
for (layer = 2; layer <= k+1; layer++) {
dpnow.clear();
for (int i = 1; i <= n; i++)
dpnow.push_back(OO);
DCT(layer, n, 1, n);
dpprev = dpnow;
}
cout << dpnow.back() << "\n";
bool ap = 0;
int x = n;
while (dprev[x] != 1) {
cout << (ap ? " " : "") << dprev[x];
ap = 1;
x = dprev[x];
}
cout << "\n";
}
