#include <bits/stdc++.h>
/*
--> Author: Kazuki_Hoshino__8703 <-- (modified: added trace output)
I love Nanasaki Ai ☆*: .｡. o(≧▽≦)o .｡.:*☆
*/
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
using namespace std;
const int mn = 3e3 + 5;
const int inf = 1e18;
int n, k, a[mn], dp[mn][mn], prefix[mn], par[mn][mn];
// dp[i][j] = max(dp[i - 1][j1] + (prefix[j] - prefix[j1]) * (prefix[n] - prefix[j]))
struct line{
double x, y;
int fi;
};
double center(line a, line b){
return (a.y - b.y) / (b.x - a.x);
}
deque <line> reina;
deque <pair<double, int>> pts;
void add(line kumiko){
while(reina.size() >= 1 && kumiko.x == reina.front().x && kumiko.y >= reina.front().y){
reina.pop_front();
pts.pop_front();
}
while(reina.size() >= 2 && center(kumiko, reina.front()) >= pts.front().fi){
reina.pop_front();
pts.pop_front();
}
if(pts.size()) pts.push_front({center(reina.front(), kumiko), kumiko.fi});
else pts.push_front({1e9, kumiko.fi});
reina.push_front(kumiko);
}
pii query(int x){
if(pts.empty()) return {-inf, 0};
int id = upper_bound(pts.begin(), pts.end(), pair<double,int>((double)x, 0),
[](const pair<double,int>& val, const pair<double,int>& elem){
return val.first < elem.first;
}
) - pts.begin();
return {(int)reina[id].x * x + reina[id].y, pts[id].se};
}
void solve(){
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
prefix[i] = prefix[i - 1] + a[i];
}
fill(&dp[0][0], &dp[0][0] + mn * mn, -inf);
dp[0][0] = 0;
for(int i = 1; i <= k + 1; i++){
reina.clear();
pts.clear();
if(dp[i - 1][i - 1] != -inf){
line y = { (double)prefix[i - 1], (double)- dp[i - 1][i - 1], i - 1};
add(y);
}
for(int j = i; j <= n - (k + 1 - i); j++){
int val = prefix[n] - prefix[j];
pii best = query(val);
dp[i][j] = - best.fi + prefix[j] * (prefix[n] - prefix[j]);
par[i][j] = best.se;
if(dp[i - 1][j] != -inf){
line x = { (double)prefix[j], (double)- dp[i - 1][j], j};
add(x);
}
}
}
cout << dp[k + 1][n] << '\n';
if(dp[k + 1][n] == -inf){
return;
}
vector<int> cuts;
int ci = k + 1;
int cj = n;
while(ci > 0){
cuts.push_back(cj);
int prev = par[ci][cj];
cj = prev;
ci--;
}
reverse(cuts.begin(), cuts.end());
vector<int> out;
for(int x : cuts) if(x > 0) out.push_back(x);
if(out.size() > 1){
for(int idx = 0; idx < (int)out.size() - 1; idx++){
if(idx) cout << ' ';
cout << out[idx];
}
cout << '\n';
}
else{
cout << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
// cin >> t;
while(t--){
solve();
}
}
