#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e3+9,K=209,MX=1e9+9;
ll n,k,ans=-MX,idx;
ll pre[inf],a[inf];
pair<ll,ll> dp[K][inf];
vector<ll> split;
bool Q ;
struct Line {
mutable ll m, p, k,idx;
bool operator<(const Line& o) const {
return Q ? k < o.k : m < o.m;
}
};
struct LineContainer : multiset<Line> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b);
}
bool isect(iterator x, iterator y) {
if (y == end()) {
x->k = inf;
return false;
}
if (x->m == y->m)
x->k = x->p > y->p ? inf : -inf;
else
x->k = div(y->p - x->p, x->m - y->m);
return x->k >= y->k;
}
void add(ll m, ll p,ll idx) {
auto z = insert({m, p, 0,idx}), 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)->k >= y->k)
isect(x, erase(y));
}
pair<ll,ll> query(ll x) {
if(empty())
return {-MX,0};
assert(!empty());
Q = 1; auto l = *lower_bound({0,0,x}); Q = 0;
return make_pair(l.m * x + l.p,l.idx);
}
};
int main(){
cin>>n>>k;
for(ll i=1;i<=n;i++)
cin>>a[i],pre[i]=pre[i-1]+a[i];
for(ll j=1;j<=k;j++){
LineContainer lc;
lc.add(0,0,0);
for(ll i=1;i<=n;i++){
dp[j][i] = lc.query(pre[i]);
dp[j][i].first += pre[i]*pre[n] - pre[i]*pre[i] ;
lc.add(pre[i],dp[j-1][i].first-pre[i]*pre[n],i);
}
}
for(ll i=1;i<=n;i++)
if(ans<dp[k][i].first)
ans=dp[k][i].first,idx=i;
split.push_back(idx);
for(ll j=k;j>1;j--)
idx=dp[j][idx].second,split.push_back(idx);
reverse(split.begin(),split.end());
cout<<ans<<endl;
for(auto o:split)
cout<<o<<" ";
cout<<endl;
}
