#include<bits/stdc++.h>
using namespace std;
struct node{
long long score = -1,cur = -1,prev = -1;
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin>>n>>k;
vector<long long>arr(n);
for (int i = 0;i<n;++i)cin>>arr[i];
vector<long long>pref(n + 1,0);
for (int i = 0;i<n;++i){
pref[i + 1] = pref[i] + arr[i];
}
vector<vector<node>>dp(n + 1,vector<node>(k + 1));
auto getscore = [&](int l,int r){
return pref[r] - pref[l];
};
for (int i = 0;i<n;++i){
dp[i][0] = {0,i,-1};
}
for (int i = 1;i<n;++i){
for (int j = 1;j<=k;++j){
for (int p = 0;p < i;++p){
if (j > 1 && p == 0)continue;
if (dp[p][j - 1].cur == -1)continue;
if (dp[i][j].score < dp[p][j - 1].score + getscore(dp[p][j - 1].cur,i) * getscore(i,n)){
dp[i][j] = {dp[p][j - 1].score + getscore(dp[p][j - 1].cur,i) * getscore(i,n),i,p};
}
}
}
}
node ans;
for (int i = 1;i<n;++i){
if (dp[i][k].score > ans.score && dp[i][k].cur==i){
ans = dp[i][k];
}
}
vector<int>ind;
int p = k - 1;
cout<<ans.score<<'\n';
for (int i = 0;i<k;++i){
ind.push_back(ans.cur);
if (i!=k - 1){
ans = dp[ans.prev][p];
--p;
}
}
reverse(ind.begin(),ind.end());
for (auto x:ind)cout<<x<<" ";
cout<<'\n';
return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/
