#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=1e5+9;
ll n,K,pos,a[MX],dp[MX],dp1[MX],p[MX];
vector<ll>M,B;
vector<int>ID;
int fdp[202][MX];
bool bad(ll m1,ll b1,ll m2,ll b2,ll m3,ll b3){
return 1.0*(b1-b3)*(m2-m1)<1.0*(b1-b2)*(m3-m1);
}
void add(ll m,ll b,ll idx){
while(M.size()>=2&&bad(M[M.size()-2],B[B.size()-2],M[M.size()-1],B[B.size()-1],m,b))
M.pop_back(),B.pop_back(),ID.pop_back();
M.push_back(m);
B.push_back(b);
ID.push_back(idx);
}
pair<ll,int> query(ll x){
if(pos>(int)M.size()-1)pos=(int)M.size()-1;
while(pos+1<(int)M.size()&&1.0*M[pos+1]*x+B[pos+1]>=1.0*M[pos]*x+B[pos])pos++;
return {M[pos]*x+B[pos],ID[pos]};
}
int main(){
cin>>n>>K;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
p[i]=p[i-1]+a[i];
}
for(int i=1;i<=K;i++){
B.clear();
M.clear();
ID.clear();
pos=0;
add(p[i],-p[i]*p[i]+dp[i],i);
for(int j=i+1;j<=n;j++){
if(j>i+1&&p[j]==p[j-1]){
dp1[j]=dp1[j-1];
fdp[i][j]=fdp[i][j-1];
continue;
}
pair<ll,int>ans=query(p[j]);
dp1[j]=ans.first;
fdp[i][j]=ans.second;
add(p[j],-p[j]*p[j]+dp[j],j);
}
for(int k=1;k<=n;k++)dp[k]=dp1[k];
}
printf("%lld\n",dp[n]);
for(int i=K,j=n;i>=1;i--){
j=fdp[i][j];
printf("%d ",j);
}
}
