#include <bits/stdc++.h>
using namespace std;
constexpr int maxn=1e3 + 5;
constexpr int maxk=205;
long long dp[maxn][maxk]; //max wynik jezeli lacznie podzielilem j razy a ostatnio bylo po indeksie i
pair<int,int> back[maxn][maxk]; //z jakiego stanu wzialem wynik
long long P[maxn];
long long sum(int i,int j){
if (i==0) return P[j];
return P[j]-P[i-1];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,k;
cin>>n>>k;
vector<int> l(n);
for (int i=0;i<n;i++){
cin>>l[i];
if (i>0) P[i]=l[i]+P[i-1];
else P[i]=l[i];
}
dp[0][1]=sum(0,0)*sum(1,n-1);
for (int j=1;j<=k;j++){
for (int i=j-1;i<n-1;i++){
for (int l=0;l<i;l++){
if (dp[l][j-1] + sum(l+1,i)*sum(i+1,n-1) >= dp[i][j]){
dp[i][j]=dp[l][j-1] + sum(l+1,i)*sum(i+1,n-1);
back[i][j]={l,j-1};
}
}
}
}
long long ans=-2e18;
pair<int,int> state;
for (int i=0;i<n;i++){
if (dp[i][k]>ans){
ans=dp[i][k];
state={i,k};
}
}
vector<int> points;
while (state.second>0){
points.push_back(state.first+1);
state=back[state.first][state.second];
}
reverse(points.begin(),points.end());
cout<<ans<<"\n";
for (int x:points) cout<<x<<" ";
cout<<"\n";
return 0;
}
