#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
struct line {
ll k, m, id;
ll eval (ll x) {return x * k + m;}
ll its (line u) {
if (u.k == k)
return oo;
return (m - u.m) / (u.k - k);
}
};
bool check (line a, line b, line c){
return (a.m - b.m) * (c.k - a.k) <= (a.m - c.m) * (b.k - a.k);
}
int n,i,j,s;
ll a[N],ans;
deque <line> q[203];
int trace[N][203];
vector <int> res;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// #ifndef ONLINE_JUDGE
// freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
// #endif
cin >> n >> s;
forr (i,1,n)
cin >> a[i], a[i] += a[i - 1];
forr (i,0,201)
q[i].pb({0,0,0});
s++;
forr (i,1,n){
ford (j,s,1){
while (q[j].size() >= 2 && q[j].back().eval(a[i]) <= q[j][q[j].size() - 2].eval(a[i]))
q[j].pop_back();
ll f = q[j].back().eval(a[i]);
ans = max (ans,f);
//cout << f << " " << q[j].back().id << " ";
trace[i][j] = q[j].back().id;
line cur = {a[i],-a[i] * a[i] + f,i};
while (q[j + 1].size() >= 2 && check (cur,q[j + 1][0],q[j + 1][1]))
q[j + 1].pop_front();
q[j + 1].push_front(cur);
}
// cout << "\n";
}
cout << ans << '\n';
int i = n, j = s;
while (trace[i][j] != 0){
res.pb(trace[i][j]);
i = trace[i][j];
j--;
}
reverse(all(res));
for (int w : res)
cout << w << " ";
return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/
