#include <bits/stdc++.h>
using namespace std;
#define ll long long
int const N=2e5+5;
int const mod=1e9+7;
int m, n;
vector<long long> dp_before, dp_cur;
vector<int> dp_pr;
vector<long long> dp[205];
vector<int> pr[N];
long long prefix[N];
vector<int> mv;
long long C(int i, int j){
if(i==0)
return prefix[j]*prefix[j];
return (prefix[j]-prefix[i-1])*(prefix[j]-prefix[i-1]);
}
// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr) {
if (l > r)
return;
int mid = (l + r) >> 1;
pair<long long, int> best = {LLONG_MAX, -1};
for (int k = optl; k <= min(mid, optr); k++) {
best = min(best, {(k ? dp_before[k - 1] : 0) + C(k, mid), k});
}
dp_cur[mid] = best.first;
dp_pr[mid]= best.second;
int opt = best.second;
compute(l, mid - 1, optl, opt);
compute(mid + 1, r, opt, optr);
}
long long solve() {
dp_before.assign(n,0);
dp_cur.assign(n,0);
dp_pr.assign(n,0);
for (int i = 0; i < n; i++)
dp_before[i] = C(0, i);
dp[0]=dp_before;
pr[0]=dp_pr;
for (int i = 1; i < m; i++) {
compute(0, n - 1, 0, n - 1);
dp[i]=dp_cur;
pr[i]=dp_pr;
dp_before = dp_cur;
}
int t=pr[m-1][n-1];
for(int i=m-2;i>=0;i--){
mv.push_back(pr[i][t]);
t=pr[i][t];
}
return dp_before[n - 1];
}
int main(){
cin>>n>>m;
m++;
long long total=0;
int arr[n];
for (int i = 0; i < n; ++i){
cin>>arr[i];
total+=arr[i];
}
prefix[0]=arr[0];
for (int i = 1; i < n; ++i)
prefix[i]=prefix[i-1]+arr[i];
total*=total;
total-=solve();
total/=2;
cout<<total<<endl;
reverse(mv.begin(), mv.end());
for(auto i:mv)
cout<<i+1<<' ';
cout<<endl;
return 0;
}
