#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll n, m, a[100100], pref[100100];
int pr[100100][210];
struct line{
ll k, b;
int pos;
inline ll eval(ll x){
return k*x+b;
}
};
inline ll intersect(line l1, line l2){
return (l1.b-l2.b)/(l2.k-l1.k);
}
inline bool to_erase(line l1, line l2, line l3){
ll x = intersect(l1, l3);
return l2.eval(x) <= l3.eval(x);
}
int sz1, sz2;
line vec[100100], vecCur[100100];
inline void insrt(line ln){
if (sz1 && vec[sz1-1].k == ln.k){
if (vec[sz1-1].b < ln.b)
sz1--; else
return;
}
while(sz1 > 2 && to_erase(vec[sz1-2], vec[sz1-1], ln))
sz1--;
vec[sz1] = ln;
++sz1;
}
void swp(){
swap(vec, vecCur);
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++)
insrt({pref[i], -(pref[i]*pref[i]), i});
swp();
ll ans = 0;
for (int ii = 1; ii <= m; ii++){
int pos = 0;
for (int i = ii+1; i <= n; i++){
while(pos+1 < sz2 && vecCur[pos+1].pos < i && vecCur[pos].eval(pref[i]) <= vecCur[pos+1].eval(pref[i]))
++pos;
pr[i][ii] = vecCur[pos].pos;
ans = vecCur[pos].eval(pref[i]);
insrt({pref[i], ans-(pref[i]*pref[i]), i});
}
swp();
}
cout << ans << endl;
vector <int> vecAns;
int x = n, y = m;
while(x != 0){
x = pr[x][y];
y--;
vecAns.push_back(x);
}
vecAns.pop_back();
for (int i = vecAns.size()-1; i >= 0; i--)
cout << vecAns[i] << ' ';
}
/**
7 3
4 1 3 4 0 2 3
*/
