#pragma GCC optimize ("03,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int const MAX=1e5+5;
long long dp[MAX][2];
int ult[MAX][205];
long long sp[MAX];
int n,k;
void read(){
cin>>n>>k;
++k;
int i;
for(i=1;i<=n;++i){
cin>>sp[i];
sp[i]+=sp[i-1];
}
}
long long aa(int i){
return sp[i];
}
long long bb(int i,int dim){
return dp[i][dim]-sp[i]*sp[i];
}
double inters(int i,int j,int dim){
return 1.0*(bb(j,dim)-bb(i,dim))/(aa(i)-aa(j));
}
void get_dp(){
int i,j;
for(j=2;j<=k;++j){
deque<int>deq;
deq.push_back(j-1);
int nou=(j&1);
int vechi=1-nou;
for(i=j;i<=n;++i){
while(deq.size()>1 && inters(deq[0],deq[1],vechi)<=1.0*sp[i])
deq.pop_front();
int ind=deq[0];
dp[i][nou]=bb(ind,vechi)+aa(ind)*sp[i];
ult[i][j]=ind;
if(sp[deq.back()]==sp[i]){
ind=deq.back();
if(bb(i,vechi)<=bb(ind,vechi))
continue;
deq.pop_back();
}
while(deq.size()>1 && inters(deq.back(),deq[deq.size()-2],vechi)>=inters(i,deq.back(),vechi))
deq.pop_back();
deq.push_back(i);
}
}
}
void write(){
cout<<dp[n][k&1]<<'\n';
stack<int>stv;
int i;
int ind=n;
for(i=k;i>1;--i){
ind=ult[ind][i];
stv.push(ind);
}
while(!stv.empty()){
cout<<stv.top()<<' ';
stv.pop();
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
read();
get_dp();
write();
return 0;
}
