#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 30, MOD = 1e9 + 7;
int n,k;
int a[N];
ll pref[N],sf[N];
int p[N][203];
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){
int l = -1,r = (int)st.size() - 1;
while(r - l > 1){
int mid = (l + r) >> 1;
if(mid == (int)st.size() - 1 || (st[mid].b - st[mid + 1].b) * 1.0 >= x * 1.0 * (st[mid + 1].k - st[mid].k)){
r = mid;
}else{
l = mid;
}
}
return {st[r].get(x),st[r].pos};
}
set<int> St;
void test(){
cin >> n >> k;
for(int i = 1;i <= n;i++){
cin >> a[i];
St.insert(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});
int it = 1;
auto ok = [&](int mid,int j){
return (mid == (int)st.size() - 1 || (st[mid].b - st[mid + 1].b) * 1.0 >= sf[j + 1] * 1.0 * (st[mid + 1].k - st[mid].k));
};
for(int j = 1;j <= n;j++){
while(it < (int)st.size() - 1 && !ok(it + 1,j)){
it++;
}
while(it >= 0 && (it == (int)st.size() - 1 || (st[it].b - st[it + 1].b) * 1.0 >= sf[j + 1] * 1.0 * (st[it + 1].k - st[it].k))){
it--;
}
pair<ll,ll> G = {st[it + 1].get(sf[j + 1]),st[it + 1].pos};
dp[j] = G.first+ pref[j] * sf[j + 1];
p[j][i] = G.second;
if(!p[j][i] && i != 1){
p[j][i] = j - 1;
}
line nv = {-pref[j],tdp[j],j};
add(st,nv);
it = min(it,(int)st.size() - 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(ps){
f.push_back(ps);
St.erase(ps);
ps = p[ps][k--];
}
for(int i = 1;i <= n - 1;i++){
if(St.find(i) != St.end()&&(int)f.size() < k1){
f.push_back(i);
}
}
sort(f.begin(),f.end());
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();
}
}
