#include<bits/stdc++.h>
#define newl '\n'
const int N = 1e5 + 10;
const int K = 2e2 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;
struct Line{
long long a,b,it;
long long operator ()(long long x){
return a * x + b;
}
long long intersect(const Line &rhs) const {
if(a == rhs.a){
// std::cout << -1;
exit(0);
}
long long nume = b - rhs.b;
long long denom = rhs.a - a;
return nume / denom;
}
};
long long a[N + 1],s[N + 1],n,k;
int trace[K + 1][N + 1];
void readData(){
std::cin >> n >> k;
for(int i = 1;i <= n;++i){
std::cin >> a[i];
s[i] = s[i - 1] + a[i];
}
}
///(s[r] - s[l]) * (s[n] - s[r])
///(s[r] * s[n] - s[r] * s[r] - s[l] * s[n] + s[l] * s[r] + f[l]
///-s[r] * s[r] //meh not important
///s[r] * s[n] // also not important
///-s[l] * s[n] + s[l] * s[r] = -s[l] * s[n] + -s[l] * -s[r],-s[l] = a,(s[n] - s[r]) = x
///f[l] = b
void brute(){
std::vector<long long> pr(n + 1,0);
int it = 0;
for(int i = 1;i <= k;++i){
std::vector<long long> f(n + 1,0);
for(int j = 1;j < n;++j){
trace[i][j] = j - 1;
for(int j1 = j - 1;j1 >= 0;--j1){
long long t = (s[j] - s[j1]) * (s[n] - s[j]) + pr[j1];
if(t > f[j]){
f[j] = t;
trace[i][j] = j1;
}
if(f[j] >= f[it]){
it = j;
}
}
// if(i == 3 && j == 5){
// std::cout << f[j] << newl;
// }
}
pr.swap(f);
}
std::cout << pr[it] << newl;
int t = k;
while(t > 0){
std::cout << it << " ";
it = trace[t--][it];
}
}
bool dominate(const Line &l,const Line &o,const Line &o1){
// if(l.a == o.a && l.b == o.b){
// return true;
// }
///line lhs dominate line o
// if(l.a == o.a){
// return (l.b >= o.b);
// }
long long inter = l.intersect(o);
long long inter1 = o.intersect(o1);
return inter >= inter1;
}
void solve(){
long long it = 0;
std::deque<Line> dq;
std::vector<long long> pr(n + 1,0);
for(int i = 1;i <= k;++i){
std::vector<long long> f(n + 1,0);
for(int j = 0;j <= n;++j){
if(j > 0 && j < n){
long long x = s[n] - s[j];
while((int)dq.size() >= 2 && dq.end()[-1](x) <= dq.end()[-2](x)){
dq.pop_back();
}
f[j] = dq.end()[-1](x) + s[j] * x;
trace[i][j] = dq.end()[-1].it;
// if(i == 3 && j == 5){
// std::cerr << "IMP " << f[j] << newl;
// }
if(f[j] >= f[it]){
it = j;
}
// if(f[j] < f[j - 1] && s[j] == s[j - 1]){
// exit(0);
// }
// std::cout << f[j] << " ";
}
Line cur = {-s[j],pr[j],j};
while((int)dq.size() > 0){
if(cur.a == dq[0].a){
if((int)cur.b >= dq[0].b){
dq.pop_front();
continue;
}
}else if((int)dq.size() > 1 && dominate(cur,dq[0],dq[1])){
dq.pop_front();
continue;
}
break;
}
if((int)dq.size() == 0 || cur.a != dq[0].a){
dq.push_front(cur);
}
}
dq.clear();
pr.swap(f);
}
std::cout << pr[it] << newl;
int t = k;
while(t > 0){
std::cout << it << " ";
it = trace[t--][it];
}
}
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);std::cout.tie(nullptr);
readData();
solve();
return 0;
}
