#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
#define int long long
#define pb push_back
#define F first
#define S second
ll dp[100010];
int red[205][100010];
struct line{
int slope;
ll c;
ll eval(int x){
return slope*1ll*x+c;
}
ld interx(line & a){
return (ld)(a.c-c)/(ld)(slope-a.slope);
}
};
line chtl[100010];
int chtr[100010];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
int a[n];
ll pref[n+1];
pref[0]=0;
for(int i=0; i< n; i++){
cin >> a[i];
pref[i+1]=pref[i]+a[i];
}
for(int j=1; j<=k; j++){
int r=n+5;
int l=n+5;
chtl[l]={-pref[j-1], dp[j]};
chtr[l]=j;
l--;
for(int i=j+1; i<=n; i++){
int x = pref[n]-pref[i-1];
while(r-l>=2){
if(chtl[r].eval(x)>chtl[r-1].eval(x))break;
r--;
}
pair<line, int> np = {{-pref[i-1], dp[i]}, i};
dp[i]=chtl[r].eval(x)+pref[i-1]*(pref[n]-pref[i-1]);
red[j][i]=chtr[r];
while(r-l>=2){
if(chtl[l+1].slope==np.F.slope){
if(chtl[l+1].c<=np.F.c){
l++;
continue;
}
else break;
}
ld inter1 = chtl[l+1].interx(chtl[l+2]);
ld inter2 = np.F.interx(chtl[l+2]);
if(inter2<inter1)break;
l++;
}
chtl[l]=np.F;
chtr[l]=np.S;
l--;
}
}
ll ans=0;
int ind=0;
for(int i=1; i<=n; i++){
if(dp[i]>=ans){
ans=dp[i];
ind=i;
}
}
cout << ans << '\n';
vector<int> con;
con.pb(ind);
for(int i=k; i>1; i--){
con.pb(red[i][ind]);
ind=red[i][ind];
}
sort(con.begin(), con.end());
for(int i=0; i<k; i++){
cout << con[i]-1 << " ";
}
cout << '\n';
}
