#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, k;
int sum[100005];
int num[100005];
struct line {
int m, c;
int y(int x) {
return m*x+c;
}
};
int divv(int a, int b) {
return a/b - ((a^b)<0 && a%b);
}
int isect(line a, line b) {
if(a.m==b.m) return a.c<=b.c ? -1e18:1e18;
return divv(a.c-b.c, b.m-a.m);
}
deque<pair<line, int>> cht;
int dp[100005][2];
pair<int,int> query(int x) {
while(cht.size()>1 && cht[0].first.y(x)<=cht[1].first.y(x)) cht.pop_front();
return {cht.front().first.y(x), cht.front().second};
}
void insert(line a, int i) {
while(cht.size()>1 && isect(cht[cht.size()-2].first, cht.back().first)>=isect(cht[cht.size()-2].first, a)) cht.pop_back();
cht.push_back({a, i});
}
int32_t idx[100005][1002];
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin>>n>>k;
for(int i=1;i<=n;i++) {
cin>>num[i];
sum[i] = sum[i-1]+num[i];
}
int cur = 0;
for(int i=0;i<k;i++) {
cht.clear();
insert({0, 0}, 0);
for(int j=1;j<=n;j++) {
auto p = query(sum[j]);
dp[j][cur] = p.first;
idx[j][i] = p.second;
insert({sum[j], dp[j][1-cur]-(sum[j]*sum[j])}, j);
}
cur = 1-cur;
}
cout<<dp[n][1-cur]<<'\n';
vector<int> ans;
cur = n;
for(int i=k-1;i>=0;i--) {
ans.push_back(idx[cur][i]);
cur = idx[cur][i];
}
for(int i=k-1;i>=0;i--) cout<<ans[i]<<' ';
}
/*
7 3
4 1 3 4 0 2 3
*/
