#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define N 100005
#define oo 1e15
typedef pair<long long, long long> ii;
typedef pair<long long, pair<long long, long long>> iii;
vector<long long> cur, lst;
long long pre[N], suf[N];
int par[201][N], n, k;
struct cht{
deque<int> q;
long long get(int pos, long long x){
ii tmp = {pre[pos], lst[pos]};
return tmp.fi * x + tmp.se;
}
bool cal(int x, int y, int z){
ii a = {pre[x], lst[x]};
ii b = {pre[y], lst[y]};
ii c = {pre[z], lst[z]};
return ((long long) 1ll * (c.se - a.se) * (b.fi - c.fi) >= 1ll * (c.se - b.se) * (a.fi - c.fi));
}
void add(long long a, long long b, int pos){
int nw = pos;
while ((int) q.size() >= 2 && cal(q[(int)q.size() - 2], q[(int)q.size() - 1], nw)) q.pop_back();
q.push_back(nw);
}
ii get(long long pos){
if (!(int) q.size()) return {0, 0};
while ((int) q.size() >= 2 && get(q[0], pos) <= get(q[1], pos)) q.pop_front();
return {q[0], get(q[0], pos)};
}
void reset(){
q.clear();
}
} c1;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> k;
for (int i = 1; i <= n; i++){
cin >> pre[i];
pre[i] = pre[i - 1] + pre[i];
}
for (int i = 1; i <= n; i++){
suf[i] = pre[n] - pre[i - 1];
}
cur.resize(n + 1, 0);
lst.resize(n + 1, 0);
for (int i = 1; i <= k; i++){
lst = cur;
c1.reset();
c1.add(pre[i - 1], lst[i - 1], i - 1);
for (int j = i; j <= n; j++){
ii gt = c1.get(-suf[j + 1]);
par[i][j] = gt.fi;
cur[j] = gt.se + suf[j + 1] * pre[j];
c1.add(pre[j], lst[j], j);
}
}
long long res = -oo; int pos = 0, nn = k;
for (int i = 1; i <= n; i++){
if (cur[i] > res){
res = cur[i];
pos = i;
}
}
vector<int> vec;
vec.push_back(pos);
for (int i = k; i >= 2; i--){
vec.push_back(par[i][pos]);
pos = par[i][pos];
}
sort(vec.begin(), vec.end());
cout << res << "\n";
for (auto x : vec) cout << x << " ";
return 0;
}
