#include <bits/stdc++.h>
using namespace std;
deque<pair<long long,long long> > dq[201];
deque<int> id[201];
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,int num){
while(dq[num].size()>1){
if(f(dq[num][0],x)<f(dq[num][1],x)){
dq[num].pop_front();
id[num].pop_front();
}
else break;
}
return make_pair(f(dq[num][0],x),id[num][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,int num) {//insert line y=mx+c
pair<long long,long long> line=make_pair(m,c);
while (dq[num].size()>1) {
long long s=dq[num].size();
if (intersect(dq[num][s-1],line)<=intersect(dq[num][s-2],line)){
dq[num].pop_back();
id[num].pop_back();
}
else break;
}
dq[num].push_back(line);
id[num].push_back(index);
}
long long n,k;
long long arr[100001],pre[100001];
int dp[100001][201];
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];
for (int i=0;i<=k;i++){
ins(0,0,0,i);
}
long long ans=-1,pos=1;
for (int i=1;i<n;i++){
for (int j=k;j>=1;j--){
pair<long long,int> cur=qry(pre[i]-pre[n],j-1);
cur.first+=pre[i]*(pre[n]-pre[i]);
//dp[x][j-1].first+(pre[i]-pre[x])*(pre[n]-pre[i]);
ins(pre[i],cur.first,i,j);
dp[i][j]=cur.second;
assert(i!=cur.second);
if (j==k){
if (cur.first>=ans){
ans=cur.first;
pos=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--;
}
}
}
