#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
struct Line {
mutable long long k, m, p; // slope, intercept, last optimal x (breakpoint)
int id; // label/index for this line
// order by slope for the multiset
bool operator<(const Line& o) const { return k < o.k; }
// order by x for lower_bound(x) (heterogeneous lookup via less<>)
bool operator<(long long x) const { return p < x; }
};
// Max hull; for min hull, negate k and/or m appropriately.
struct LineContainer : multiset<Line, less<>> {
static const long long INF = (1LL<<62); // large sentinel (fits in ll)
// floored division: floor(a / b), valid for negative a,b as well
static long long floordiv(long long a, long long b) {
// b must not be 0
long long q = a / b;
long long r = a % b;
// If signs differ and remainder not zero, floor rounds down (more negative)
if ((r != 0) && ((a ^ b) < 0)) --q;
return q;
}
// set x->p = intersection point with y; return true if x's breakpoint >= y's
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = INF; return false; }
if (x->k == y->k) {
x->p = (x->m > y->m) ? INF : -INF; // keep better line
} else {
// ceil division is not needed here; KACTL uses floordiv for max hull
// Breakpoint is the last x where x is better than y:
// kx + m >= ky + my => (k - ky) x >= (my - m)
// x >= (my - m) / (k - ky)
x->p = floordiv(y->m - x->m, x->k - y->k);
}
return x->p >= y->p;
}
// insert y = kx + m with label 'id'
void add(long long k, long long m, int id) {
auto z = insert({k, m, 0, id}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
}
// returns {best_id, best_value} at x
pair<int,long long> query(long long x) const {
assert(!empty());
auto l = *lower_bound(x); // uses Line::<(long long)
long long val = l.k * x + l.m;
return {l.id, val};
}
};
// to use:
// LineContainer hull;
// hull.add(m, c);
// hull.query(x);
// to convert max queries to min queries:
// hull.add(-m, -c);
// -hull.query(x);
LineContainer hull[205];
int n,k;
signed main(){
cin>>n>>k;
vector<int> v(n+1,0), p(n+1, 0);
for(int i=1;i<=n;i++){
cin>>v[i];
p[i]=p[i-1]+v[i];
}
vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
vector<vector<pair<int,int>>> from(n+1, vector<pair<int,int>>(k+1));
for(int m=0;m<=k;m++){
hull[m].add(0, 0, 0);
}
int ans=0,a,b;
for(int i=1;i<=n;i++){
for(int m=k;m>=1;m--){
auto [id, best]=hull[m-1].query(p[i]);
int add=-p[i]*p[i]+p[i]*p[n];
dp[i][m]=best+add;
from[i][m]={id, m-1};
if(dp[i][m] > ans){
ans=dp[i][m];
a=i,b=m;
}
hull[m].add(p[i], dp[i][m]-p[i]*p[n], i);
//~ printf("i:%lld, splits:%lld, best %lld add %lld\n",i,m,best,add);
//~ printf("added m=%lld, c=%lld\n", p[i], dp[i][m]-p[i]*p[n]);
}
}
cout<<ans<<'\n';
while(a>0 and b>0){
cout<<a<<" ";
tie(a,b)=from[a][b];
}
}
/*
4 2
3 1 2 3
*/
