#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct line{
ll m,b,from;
// y=mx+b;
};
deque<line> hull;
bool check(line l1,line l2,line l3){
//intersection(l1,l2)>=intersection(l2,l3)
// x>=intersection(l2,l3) uyd l3>l2
// x<=intersection(l1,l2) uyd l1>l2
// l2 urgelj l1,l3 iin door baih tul hereggui
// ll x1=(l2.b-l1.b)/(l2.m-l1.m);
// ll x2=(l3.b-l2.b)/(l3.m-l2.m);
if(l2.m==l3.m){
if(l2.b<=l3.b) return true;
return false;
}
if((l2.b-l1.b)*(l3.m-l2.m)>=(l3.b-l2.b)*(l2.m-l1.m)) return true;
return false;
}
void add(ll m,ll b,ll from){
line l={m,b,from};
while(hull.size()>=2 and check(hull[hull.size()-2],hull[hull.size()-1],l)){
hull.pop_back();
}
hull.push_back(l);
}
pair<ll,ll> query(ll x){
while(hull.size()>=2 and hull[0].m*x+hull[0].b<=hull[1].m*x+hull[1].b){
hull.pop_front();
}
return {hull[0].m*x+hull[0].b,hull[0].from};
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0);
ll n,k,i,j,q;
cin>>n>>k;
vector<ll> a(n+1);
vector<ll> pre(n+2,0);
for(i=1 ; i<=n ; i++) cin>>a[i];
for(i=1 ; i<=n ; i++) pre[i]=pre[i-1]+a[i];
vector<vector<ll>> dp(k+1,vector<ll>(n+1,0));
vector<vector<ll>> par(k+1,vector<ll>(n+1));
vector<ll> path;
for(i=1 ; i<=k ; i++){
hull.clear();
add(0,0,0);
for(j=1 ; j<=n ; j++){
// dp[i][j]=pre[q]*pre[j]+dp[i-1][q]-pre[q]^2
// y=m*x+b;
pair<ll,ll> val=query(pre[j]);
dp[i][j]=val.first;
par[i][j]=val.second;
add(pre[j],dp[i-1][j]-pre[j]*pre[j],j);
}
}
ll u=n;
for(i=k ; i>=1 ; i--){
path.push_back(par[i][u]);
u=par[i][u];
}
cout<<dp[k][n]<<"\n";
for(auto v:path) cout<<v<<" ";
return 0;
}
