#include<bits/stdc++.h>
#define ll long long
#define MAXN 100007
using namespace std;
struct line
{
bool active=false;
ll k, n;
ll pos;
ll eval(ll x)
{
return k*x+n;
}
};
ll sz;
vector<ll>x;
line seg[4*MAXN+7];
void makeSeg(int n1)
{
sz=(1<<((int)ceil(log2(n1))));
while(x.size()<sz) x.push_back(0);
sort(x.begin(),x.end());
for(int i=1;i<2*sz;i++) seg[i].active=false;
}
void addLine(line l1, int node, int l, int r)
{
int mid=(l+r)/2;
if(!seg[node].active)
{
seg[node]=l1;
return;
}
ll elnew = l1.eval(x[l]), ernew=l1.eval(x[r]);
ll elold = seg[node].eval(x[l]), erold=seg[node].eval(x[r]);
if(elnew<=elold && ernew<=erold) return;
else if(elnew>=elold && ernew>=erold)
{
seg[node]=l1;
return;
}
if(elnew<=elold) swap(seg[node],l1);
if(l1.eval(x[mid])>=seg[node].eval(x[mid]))
{
addLine(seg[node],2*node+1,mid+1,r);
seg[node]=l1;
}
else
{
addLine(l1,2*node,l,mid);
}
}
pair<ll,int>getAns(ll xx, int node, int l, int r)
{
if(!seg[node].active) return make_pair(-1000000000000,1);
if(l==r) return make_pair(seg[node].eval(xx), seg[node].pos);
pair<ll, int> ans=make_pair(seg[node].eval(xx), seg[node].pos);
int mid=(l+r)/2;
if(xx<=x[mid]) ans=max(ans,getAns(xx,2*node,l,mid));
else ans=max(ans,getAns(xx,2*node+1,mid+1,r));
return ans;
}
struct query
{
int type;
line l;
int x;
};
ll a[MAXN];
ll dp[203][MAXN]={};
ll back[203][MAXN]={};
ll pref[MAXN];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
pref[0]=0;
for(int i=1;i<=n;i++) pref[i]=a[i]+pref[i-1];
for(int i=1;i<=n;i++) x.push_back(pref[i]);
for(int i=0;i<=n;i++)
{
for(int j=0;j<=k;j++)
{
back[j][i]=1;
}
}
for(int i=1;i<=k;i++)
{
makeSeg(n);
for(int j=1;j<=n;j++)
{
line l;
l.active=true;
l.pos=j-1;
l.n=dp[i-1][j-1]-pref[j-1]*pref[j-1];
l.k=pref[j-1];
addLine(l,1,0,sz-1);
back[i][j]=getAns(pref[j],1,0,sz-1).second;
dp[i][j]=getAns(pref[j],1,0,sz-1).first;
}
}
cout<<dp[k][n]<<endl;
vector<int>t;
while(k>0)
{
t.push_back(back[k][n]);
k--;
n=back[k][n];
}
while(!t.empty())
{
cout<<t.back()<<" ";
t.pop_back();
}
}
