#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define N ((ll)101*1000)
#define K ((ll)210)
#define INF ((ll)2e18)
int n,k,a[N],bst[K][N];
ll prt[N],dp[N],sum2;
vector <pair<pair<ll,ll>,int> > v;
ld barkhord(pair<ll,ll> x,pair<ll,ll> y){return (ld)(x.second-y.second)/(y.first-x.first);}
void add(ll a,ll b,int id)
{
while(v.size()>1 && barkhord({a,b},v[(int)v.size()-2].first)<=barkhord(v.back().first,v[(int)v.size()-2].first))v.pop_back();
v.push_back({{a,b},id});
}
pair <ll,ll> solve(ll x)
{
int l=-1,r=(int)v.size()-1;
while(l<r-1)
{
int mid=(l+r)/2;
if(barkhord(v[mid].first,v[mid+1].first)>=x)r=mid;
else l=mid;
}
return {v[r].first.first*x+v[r].first.second,v[r].second};
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>k;
for(int i=0;i<n;i++)cin>>a[i],prt[i]=(i?prt[i-1]:0)+a[i],dp[i]=prt[i]*prt[i],sum2+=a[i]*a[i];
for(int _=0;_<k;_++)
{
v.clear();
add(0,0,-1);
for(int i=0;i<n;i++)
{
pair <ll,ll> ex;ex=solve(prt[i]);
// cout<<-prt[i]<<" "<<dp[i]+prt[i]*prt[i]<<"\n";
add(-2*prt[i],dp[i]+prt[i]*prt[i],i);
dp[i]=ex.first+prt[i]*prt[i];
bst[_][i]=ex.second;
}
}
cout<<(prt[n-1]*prt[n-1]-dp[n-1])/2<<"\n";
int now=n-1;
vector <ll> res;
for(int i=k-1;i>=0;i--)
{
now=bst[i][now];
res.push_back(now+1);
}
reverse(res.begin(),res.end());
for(auto u:res)cout<<u<<" ";
return 0;
}
