#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 1e18;
struct Line{
i64 m,c;
int i;
Line() {
cin >> m >> c;
}
Line(i64 _m,i64 _c,int _i) : m(_m),c(_c),i(_i) {}
i64 getval(i64 x){
i64 y = m*1LL*x + c;
return y;
}
i64 inc(Line L){
if(this->m == L.m){
return (this->c > L.c ? -inf : inf);
}
double x = 1.0 * (L.c - this->c) / (this->m - L.m);
// if(x < 0) return inf;
return floor(x);
}
};
struct Hull{
vector<Line> lines;
vector<i64> rng;
void init(){
lines.clear();
rng.clear();
lines.push_back(Line(0,-1,-1));
rng.push_back(inf);
// cout << "Line size is " << lines.size() << '\n';
}
void insert_line(Line L){
// removing 100% faltu lines
while(lines.size() >= 2){
i64 x = L.inc(lines.back());
i64 l = rng[rng.size() - 2] + 1;
// assert(l > -inf);
if(x < l){
lines.pop_back();
rng.pop_back();
}else{
break;
}
}
if(lines.empty()){
lines.push_back(L);
rng.push_back(inf);
}else{
i64 x = L.inc(lines.back());
if(x == inf) return;
rng[rng.size() - 1] = x;
rng.push_back(inf);
lines.push_back(L);
}
}
Line query(i64 x){
int low = lower_bound(rng.begin(),rng.end(),x) - rng.begin();
return lines[low];
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,k;
cin >> n >> k;
vector<int> a(n + 1);
for(int i = 1;i <= n;i++){
cin >> a[i];
}
vector<i64> pref(n + 1);
for(int i = 1;i <= n;i++){
pref[i] = pref[i - 1] + a[i];
}
auto S = [&](int i,int j){
return pref[j] - pref[i];
};
vector<vector<int>> best(n + 1,vector<int>(k + 1,-1));
// vector<vector<i64>> dp(n + 1,vector<i64>(k + 1,-inf));
vector<i64> cur_dp(n + 1,-inf),prev_dp(n + 1,0);
Hull hull;
hull.insert_line(Line(0,0,0));
for(int i = 1;i <= k;i++){
vector<Line> lines(n);
for(int j = 1;j < n;j++){
if(best[j][i - 1] == -1) continue;
// assert(dp[j][i - 1] >= 0);
i64 m = S(0,j);
i64 c = -m * 1LL * S(0,n) + prev_dp[j];
lines[j] = (Line(m,c,j));
}
for(int j = 1;j < n;j++){
i64 x = S(0,j);
Line ans = hull.query(x);
i64 val = ans.getval(x);
if(best[j][i - 1] != -1){
hull.insert_line(lines[j]);
}
if(val < 0) continue;
i64 C = x * 1LL * (S(0,n) - x);
cur_dp[j] = val + C;
best[j][i] = ans.i;
}
prev_dp = cur_dp;
cur_dp = vector<i64>(n + 1,-inf);
hull.init();
}
int x = 0;
i64 maxi = 0;
for(int i = n - 1;i >= 1;i--){
if(prev_dp[i] >= maxi){
x = i;
maxi = prev_dp[i];
}
}
vector<int> ans;
while((int) ans.size() < k){
ans.push_back(x);
x = best[x][k - ans.size() + 1];
}
// assert(ans.size() == k);
cout << maxi << '\n';
for(int i = ans.size() - 1;i >= 0;i--){
cout << ans[i] << " ";
}
cout << '\n';
return 0;
}
