#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,k,K,B,dp[100009],dp2[100009],f[100009],jm[100009],X;
deque <pair <pair <long long, long long>, long long> > de;
int DP[100003][203];
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>k;k++;
for(i=1; i<=a; i++){
cin>>f[i];jm[i]=jm[i-1]+f[i];
}
for(j=2; j<=k; j++){
while(de.size()) de.pop_back();
for(i=j; i<=a; i++){
K=jm[i-1];B=dp[i-1]-jm[i-1]*jm[i-1];
while(de.size()){
if(de[de.size()-1].first.second<=B){
de.pop_back();
}else{
break;
}
}
while(de.size()>1){
zx=(B-de[de.size()-2].first.second)*(de[de.size()-2].first.first-de[de.size()-1].first.first);
xc=(de[de.size()-1].first.second-de[de.size()-2].first.second)*(de[de.size()-2].first.first-K);
if(zx>xc){
break;
}
de.pop_back();
}
de.push_back({{K,B},i-1});
X=jm[i];
while(de.size()>1){
zx=de[0].first.first*X+de[0].first.second;
xc=de[1].first.first*X+de[1].first.second;
if(zx<=xc){
de.pop_front();
}else{
break;
}
}
dp2[i]=de[0].first.first*X+de[0].first.second;
DP[i][j]=de[0].second;
}
for(i=1; i<=a; i++){
dp[i]=dp2[i];dp2[i]=0;
}
}
cout<<dp[a]<<"\n";
i=a;j=k;
while(j>1){
i=DP[i][j];j--;
cout<<i<<" ";
}
return 0;
}
