#include <bits/stdc++.h>
using namespace std;
deque<pair<long long,long long> > dq;
deque<int> id;
long long f(pair<long long,long long> line, long long x){
return line.first*x + line.second;
}
pair<long long,int> qry(long long x){
while(dq.size()>1){
if(f(dq[0],x)<f(dq[1],x)){
dq.pop_front();
id.pop_front();
}
else break;
}
return make_pair(f(dq[0],x),id[0]);
}
long double intersect(long long m1, long long c1, long long m2, long long c2){
return (long double)(c2-c1)/(m1-m2);
}
long double intersect(pair<long long,long long> p1, pair<long long,long long> p2){
return intersect(p1.first,p1.second,p2.first,p2.second);
}
void ins(long long m,long long c,int index) {//insert line y=mx+c
pair<long long,long long> line=make_pair(m,c);
while (dq.size()>1) {
long long s=dq.size();
if (intersect(dq[s-1],line)<=intersect(dq[s-2],line)){
dq.pop_back();
id.pop_back();
}
else break;
}
dq.push_back(line);
id.push_back(index);
}
long long n,k;
long long arr[100001],pre[100001];
int dp[100001][201];
long long dp2[100001];
bool vis[100001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>k;
for (int i=1;i<=n;i++) cin>>arr[i];
for (int i=1;i<=n;i++) pre[i]=pre[i-1]+arr[i];
ins(0,0,0);
long long ans=-1,pos=1;
for (int j=1;j<=k;j++){
for (int i=1;i<n;i++){
pair<long long,int> cur=qry(pre[i]-pre[n]);
cur.first+=pre[i]*(pre[n]-pre[i]);
//dp[x][j-1].first+(pre[i]-pre[x])*(pre[n]-pre[i]);
dp[i][j]=cur.second;
dp2[i]=cur.first;
if (j==k){
if (cur.first>=ans){
ans=cur.first;
pos=i;
}
}
}
dq.clear();
id.clear();
ins(0,0,0);
for (int i=1;i<n;i++){
ins(pre[i],dp2[i],i);
}
}
cout<<ans<<'\n';
while (pos!=0 && k>0){
cout<<pos<<' ';
vis[pos]=true;
pos=dp[pos][k];
k--;
}
for (int i=1;i<n;i++){
if (k==0) break;
if (!vis[i]){
cout<<i<<' ';
k--;
}
}
}
