#include <bits/stdc++.h>
// #define int long long
#define fi first
#define pll pair<long long,long long>
#define se second
#define isz(x) (int)(x).size()
using namespace std;
using ll=long long;
const long long inf = 1e18;
const int mod = 1e9+7;
const int maxn = 1e4+5;
const int block = 500;
int trace[maxn][maxn],ps[maxn];
ll dp[maxn][2];
void compute(int j,int l,int r,int optl,int optr){
if (l>r)return;
int mid=(l+r)>>1;
pll best={inf,-1};
for (int i=optl;i<=min(mid,optr);++i){
int x=ps[mid]-ps[i-1];
ll val=dp[i-1][0]+x*x;
if (best.fi>=val){
best={val,i};
trace[mid][j]=i;
}
}
dp[mid][1]=best.fi;
int opt=best.se;
compute(j,l,mid-1,optl,opt);
compute(j,mid+1,r,opt,optr);
}
void test(){
int n,k; cin>>n>>k;
for (int i=1;i<=n;++i){
cin>>ps[i];
ps[i]+=ps[i-1];
dp[i][0]=ps[i]*ps[i];
}
for (int j=2;j<=k+1;++j){
compute(j,1,n,1,n);
for (int i=1;i<=n;++i)dp[i][0]=dp[i][1];
}
ll ans=(1ll*ps[n]*ps[n]-dp[n][0])/2;
cout<<ans<<"\n";
vector<int> path;
int y=k+1,x=trace[n][y];
while (y>1){
path.push_back(x-1);
x=trace[x-1][y]; --y;
}
reverse(path.begin(),path.end());
for (int i : path) cout<<i<<" ";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
test();
}
