#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,k;
cin>>n>>k;
vector<long long>all(n+1);
for(int i=1;i<=n;i++){
cin>>all[i];
}
vector<vector<long long>>dp(n+3,vector<long long>(k+1));
vector<vector<long long>>dpa(n+3,vector<long long>(k+1));
vector<long long>ps(n+3),suf(n+3);
for(int i=1;i<=n;i++){
ps[i]=ps[i-1]+all[i];
}
for(int i=n;i>=1;i--){
suf[i]=all[i]+suf[i+1];
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=k;j++){
if(j==0){
dp[i][j]=0;
continue;
}
if(j==1){
dp[i][j]=ps[i]*suf[i+1];
dpa[i][j]=-1;
continue;
}
for(int h=1;h<i;h++){
long long fake=dp[h][j-1]+(ps[i]-ps[h])*suf[i+1];
if(fake>dp[i][j]){
dp[i][j]=fake;
dpa[i][j]=h;
}
}
}
}
long long maxa=-1,w=0;
for(int i=1;i<=n;i++){
if(dp[i][k]>maxa){
w=i;
maxa=dp[i][k];
}
}
cout<<maxa<<"\n";
int now=k;
vector<int>res;
while(now>0){
res.push_back(w);
w=dpa[w][now];
now--;
}
reverse(res.begin(),res.end());
for(auto x:res){
cout<<x<<" ";
}
cout<<endl;
}
