#include <bits/stdc++.h>
using namespace std;
template<typename T>
struct LiChaoTree{
static const T identity = 0;
struct Line{
T m, c;
Line(){
m = 0;
c = identity;
}
Line(T m, T c) : m(m), c(c) {}
T val(T x){
return m*x + c;
}
};
struct Node{
Node *lc, *rc;
Line line;
int idx;
Node() : lc(0), rc(0) {}
};
deque<Node> buffer;
Node* new_node(){
buffer.emplace_back();
return &buffer.back();
}
Node *root;
T L, R;
void init(T L, T R){
this->L = L;
this->R = R;
root = new_node();
}
void insert(Node* &node, T l, T r, Line line, int idx){
if(!node){
node = new_node();
node->line = line;
node->idx = idx;
return;
}
if(r - l == 1)
return;
T mid = (l + r) >> 1;
if(line.val(mid) > node->line.val(mid)){
swap(line, node->line);
swap(idx, node->idx);
}
if(line.val(l) > node->line.val(l)) insert(node->lc, l, mid, line, idx);
else insert(node->rc, mid, r, line, idx);
}
pair<T, int> query(Node* &node, T l, T r, T x){
if(!node)
return {identity, 0};
T mid = (l + r) >> 1;
pair<T, int> res = {node->line.val(x), node->idx};
if(r - l == 1)
return res;
if(x < mid) return max(res, query(node->lc, l, mid, x));
else return max(res, query(node->rc, mid, r, x));
}
void clear(){
buffer.clear();
}
void insert(T m, T c, int idx) { insert(root, L, R, Line(m, c), idx); }
pair<T, int> query(T x) { return query(root, L, R, x); }
};
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
cin >> N >> K;
vector<int64_t> pref(N+1);
for(int i = 1; i <= N; i++){
cin >> pref[i];
pref[i] += pref[i-1];
}
for(int i = 1; i <= N; i++)
cout << pref[i] << ' ';
cout << '\n';
LiChaoTree<int64_t> dp[2];
vector<vector<int>> par(K+1, vector<int>(N+1, -1));
for(int i = 0; i < 2; i++)
dp[i].init(-1, 2'000'000'000);
int64_t temp = 0;
pair<int64_t, int> ans = {0, 0};
for(int i = 1; i <= K; i++){
int t = (i-1)&1;
dp[t^1].clear();
for(int j = 1; j < N; j++){
pair<int64_t, int> q = dp[t].query(pref[N] - pref[j]);
temp = q.first + pref[j]*(pref[N] - pref[j]);
int p = q.second;
dp[t^1].insert(-pref[j], temp, j);
ans = max(ans, {temp, j});
par[i][j] = p;
}
}
cout << ans.first << '\n';
int nxt = ans.second;
for(int i = K; i > 0; --i){
cout << nxt << ' ';
nxt = par[i][nxt];
}
return 0;
}
// dp[i][j] -> max val if the i th split is enacted on the j th place
// dp[i][j] = max over k(dp[i-1][k] + sum(k..j)*sum(j+1, n))
// dp = (pref[j])*(pref[n] - pref[j]) - pref[k]*(pref[n] - pref[j]) + dp[i-1][k];
// dp[1][1] -> (pref[n] - pref[1])*(pref[1] - pref[0]);
// dp[i][j] = max over z (dp[i-1][z] + (pref[j] - pref[z])*(pref[N] - pref[j]))\
/*
4 1 3 4 0 2 3
6 3 1
4 1 3 4 0 2 3 -> 42
4 1 3 4 0 2 -> 48
4 1 3 -> 16
*/
