#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n, k, trace[maxn + 1][201];
long long bestPos = 0, res = -1e18, pre[maxn + 1];
struct line{
long long a, b;
mutable long double p;
int id;
bool operator < (const line& other)const{
if (other.a == 1e18 && other.b == 1e18) return p < other.p;
return a < other.a || (a == other.a && b < other.b);
}
};
struct LINE_CONTAINER{
multiset<line> ms;
inline bool del(multiset<line>::iterator x, multiset<line>::iterator y){
if (y == ms.end()){
x->p = 1e18;
return false;
}
if (x->a == y->a){
x->p = (x->b >= y->b) ? 1e18 : -1e18;
}
else x->p = (long double)(y->b - x->b) / (long double)(x->a - y->a);
return x->p >= y->p;
}
inline void update(long long a, long long b, int i){
multiset<line>::iterator x = ms.insert({a, b, 0, i}), y = next(x);
while(del(x, y)) y = ms.erase(y);
if (x != ms.begin()){
y = prev(x);
if (del(y, x)) ms.erase(x);
}
else y = x;
while(y != ms.begin()){
x = prev(y);
if (del(x, y)){
del(x, ms.erase(y));
y = x;
}
else break;
}
}
inline pair<long long, int> get(long long x){
multiset<line>::iterator it = ms.lower_bound({(long long)1e18, (long long)1e18, (long double)x});
if (it == ms.end()) return {-1e18, 0};
return {it->a * x + it->b, it->id};
}
} lc[200];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i){
cin >> pre[i];
pre[i] += pre[i - 1];
}
lc[0].update(0, 0, 0);
for (int i = 0; i <= n; ++i){
for (int j = 0; j <= k; ++j) {
trace[i][j] = 0;
}
}
for (int i = 1; i <= n; ++i){
for (int j = min(i, k); j >= 1; --j){
pair<long long, int> g = lc[j - 1].get(pre[i] - pre[n]);
long long dp = g.first + pre[i] * (pre[n] - pre[i]);
if (j < k && dp != -1e18) lc[j].update((long long)pre[i], dp, i);
if (j == k && i < n && dp > res){
bestPos = i;
res = dp;
}
trace[i][j] = g.second;
}
}
cout << res << '\n';
vector<int> cuts;
while (bestPos != 0 && k > 0) {
cuts.push_back(bestPos);
bestPos = trace[bestPos][k];
--k;
}
reverse(cuts.begin(), cuts.end());
for (int x : cuts) cout << x << ' ';
return 0;
}
