#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], dprev[MAXN][MAXK], layer;
ll s[MAXN];
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, op1); op <= min(mid-1, op2); 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][layer] = theop;
DCT(a, mid-1, op1, theop), DCT(mid+1, b, theop, op2);
}
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] = s[i-1] + arr[i];
for (int i = 1; i <= n; i++)
dpprev.push_back(0);
for (layer = 1; layer <= k; 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;
layer--;
while (dprev[x][layer]) {
if (ap) cout << " ";
cout << dprev[x][layer];
ap = 1;
x = dprev[x][layer];
layer--;
}
cout << "\n";
}
