#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;
//set<line>::iterator it;
line(ll _k, ll _b, int _pos){
k = _k;
b = _b;
pos = _pos;
}
ld eval(ll x){
return k*x+b;
}
};
inline bool to_erase(line l1, line l2, line l3){
return ((l3.b-l1.b)/(l1.k-l3.k) > (l3.b-l2.b)/(l2.k-l3.k));
}
vector <line> vec, vecCur;
void insrt(line ln){
if (!vec.empty() && vec.back().k == ln.k){
if (vec.back().b < ln.b)
vec.pop_back(); else
return;
}
while((int)vec.size() > 2 && ((ln.b-vec[vec.size()-2].b)/(vec[vec.size()-2].k-ln.k) > (ln.b-vec.back().b)/(vec.back().k-ln.k)))
vec.pop_back();
vec.push_back(ln);
}
void swp(){
vec.swap(vecCur);
vec.clear();
}
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(line(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 < (int)vecCur.size() && 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(line(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
*/
