#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], pref[N];
int pr[202][N];
struct line{
long long k, b;
int pos;
inline long long val(int x){
return k * x + b;
}
};
line q1[N], q2[N];
int sz1, sz2;
inline long long intersect(line l1, line l2){
return (l1.b - l2.b) / (l2.k - l1.k);
}
inline bool Is_need_to_erase(line l1, line l2, line l3){
long long x = intersect(l1, l3);
return l2.val(x) <= l3.val(x);
}
inline void Add(line new_line){
if(sz1 && q1[sz1 - 1].k == new_line.k){
if(q1[sz1 - 1].b < new_line.b){
sz1 -= 1;
}
else{
return;
}
}
while(sz1 > 2 && Is_need_to_erase(q1[sz1 - 2], q1[sz1 - 1], new_line)){
sz1 -= 1;
}
q1[sz1] = new_line;
sz1 += 1;
}
inline void Swap(){
swap(q1, q2);
swap(sz1, sz2);
sz1 = 0;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
for(int i = 1; i <= n; i++){
Add({pref[i], -(1LL * pref[i] * pref[i]), i});
}
Swap();
long long ans = 0;
for(int i = 1; i <= m; i++){
int pos = 0;
for(int j = i + 1; j <= n; j++){
while(pos + 1 < sz2 && q2[pos + 1].pos < j && q2[pos].val(pref[j]) <= q2[pos + 1].val(pref[j])){
pos += 1;
}
pr[i][j] = q2[pos].pos;
ans = q2[pos].val(pref[j]);
Add({pref[j], ans - 1LL * pref[j] * pref[j], j});
}
Swap();
}
cout << ans << "\n";
vector < int > anss;
for(int i = m, x = n; x && i >= 1; i--){
x = pr[i][x];
anss.push_back(x);
}
reverse(anss.begin(), anss.end());
for(auto it : anss){
cout << it << " ";
}
}
