#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 30, MOD = 1e9 + 7;
int n,k;
ll a[N];
ll pref[N],sf[N];
int p[N][201];
ll dp[N],tdp[N];
struct line{
ll k,b;
int pos = 0;
ll get(ll x){
return k * x + b;
}
};
long double cross(line a,line b){
return ((a.b - b.b) * 1.0 / ((b.k - a.k) * 1.0));
}
void add(vector<line> &st,line l){
while((int)st.size() > 1 && cross(l,st[(int)st.size() - 2]) <= cross(l,st.back())){
st.pop_back();
}
st.push_back(l);
}
pair<ll,ll> get(vector<line> &st,ll x){
ll ret =0 ,pos = 0;
for(int i = 0;i < (int)st.size();i++){
if(st[i].get(x) >= ret){
ret = st[i].get(x);
pos = st[i].pos;
}
}
return {ret,pos};
}
void test(){
cin >> n >> k;
for(int i = 1;i <= n;i++){
cin >> a[i];
}
for(int i = 1;i <= n;i++){
pref[i] = pref[i - 1] + a[i];
}
for(int i = n;i >= 1;i--){
sf[i] = sf[i + 1] + a[i];
}
for(int i = 1;i <= k;i++){
vector<line> st;
add(st,{0,0});
for(int j = 1;j <= n;j++){
pair<ll,ll> G = get(st,sf[j + 1]);
dp[j] = G.first+ pref[j] * sf[j + 1];
p[j][i] = G.second;
line nv = {-pref[j],tdp[j],j};
add(st,nv);
// for(int prev = 0;prev < j;prev++){
// dp[j] = max(dp[j],tdp[prev] + pref[j] * sf[j + 1] - pref[prev] * sf[j + 1]);
// }
}
for(int j = 1;j <= n;j++){
tdp[j] = dp[j];
dp[j] =0 ;
}
}
ll res = 0;
int ps = 0;
for(int i = 1;i <= n;i++){
if(tdp[i] > res){
res = tdp[i];
ps = i;
}
}
vector<int> f;
cout << res << '\n';
int k1 = k;
while(k){
f.push_back(ps);
ps = p[ps][k--];
}
reverse(f.begin(),f.end());
assert((int)f.size() == k1);
for(int j:f){
cout << j << ' ';
}
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--){
test();
}
}
