#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n,k;
cin>>n>>k;
ll a[n+5];
for(ll i=1;i<=n;i++){
cin>>a[i];
}
ll dp[n+5][k+5];
for(ll i=0;i<=n;i++){
fill(dp[i],dp[i]+k+2,0);
}
ll sum[n+5];
sum[0]=0;
for(ll i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
}
sum[n+1]=sum[n];
ll bef[n+5][k+5];
for(ll j=1;j<=k+1;j++){
for(ll i=1;i<=n;i++){
//cout<<"CURRENT "<<i<<' '<<j<<"\n";
dp[i][j]=-1;
bef[i][j]=1;
for(ll l=0;l<i;l++){
//cout<<l<<' '<<j-1<<' '<<(sum[i]-sum[l])*(sum[n]-sum[i])<<"\n";
if(dp[l][j-1]+(sum[i]-sum[l])*(sum[n]-sum[i])>dp[i][j]){
dp[i][j]=dp[l][j-1]+(sum[i]-sum[l])*(sum[n]-sum[i]);
bef[i][j]=l;
}
}
if(bef[i][j]==0) bef[i][j]=1;
dp[i][j]=max(dp[i][j],0ll);
}
}
cout<<dp[n][k+1]<<"\n";
ll cur=n;
vector<ll>v;
for(ll i=k;i>=1;i--){
cur=bef[cur][i+1];
v.pb(cur);
}
for(ll i=v.size()-1;i>=0;i--){
cout<<v[i]<<' ';
}
}
