#include"bits/stdc++.h"
using namespace std;
#define S second
#define F first
const int mxn=1e5;
// --- coordinate compression ---
vector<long long> xs;
int SZ;
struct line{
long long m=1,b=0;
int idx=-1;
// eval at COMPRESSED index ci (looks up real x)
long long eval(int ci) const {
return m*xs[ci]+b;
}
};
struct node{
int lc=-1,rc=-1;
bool ex=0;
line li;
}tn[mxn*20];
int cnt=0;
int create(){
cnt++;
tn[cnt].ex=0; tn[cnt].lc=-1; tn[cnt].rc=-1; tn[cnt].li=line();
return cnt;
}
void upd(line li,int i,int l,int r){
int m=(l+r)/2;
auto&v=tn[i];
if(!v.ex){ v.li=li; v.ex=1; return; }
if(li.eval(m)>v.li.eval(m)) swap(li,v.li);
if(l==r) return;
if(li.eval(l)>v.li.eval(l)){
if(v.lc==-1) v.lc=create();
upd(li,v.lc,l,m);
} else if(li.eval(r)>v.li.eval(r)){
if(v.rc==-1) v.rc=create();
upd(li,v.rc,m+1,r);
}
}
pair<long long,int> qry(int x,int i,int l,int r){
auto&v=tn[i];
if(!v.ex) return {-1,-1};
auto res=make_pair(v.li.eval(x),v.li.idx);
if(l==r) return res;
int m=(l+r)/2;
if(x<=m){
if(v.lc==-1) return res;
return max(res,qry(x,v.lc,l,m));
}
if(v.rc==-1) return res;
return max(res,qry(x,v.rc,m+1,r));
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n,k;
cin>>n>>k;
int a[n+1];
long long p[n+1]={};
for(int i=1;i<=n;i++){
cin>>a[i];
p[i]=p[i-1]+a[i];
}
// build compressed x-axis from all prefix sums
xs.assign(p,p+n+1);
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
SZ=(int)xs.size();
auto ci=[&](long long v){
return (int)(lower_bound(xs.begin(),xs.end(),v)-xs.begin());
};
int pr[n+1][k+1]={};
long long dp[n+1][2]={};
for(int j=1;j<=k;j++){
create(); // root = node 1
for(int i=j+1;i<=n;i++){
// line: f(x) = p[i-1]*x + (dp[i-1][0] - p[i-1]^2)
upd(line{p[i-1], dp[i-1][0]-p[i-1]*p[i-1], i-1},
1, 0, SZ-1);
auto q=qry(ci(p[i]), 1, 0, SZ-1);
dp[i][1]=q.F;
pr[i][j]=q.S;
dp[i-1][0]=dp[i-1][1];
}
dp[n][0]=dp[n][1];
cnt=0; // reset node pool for next layer
}
cout<<dp[n][0]<<'\n';
while(k){
cout<<pr[n][k]<<' ';
n=pr[n][k]; k--;
}
}
