/*
* author : Apiram
* created: 26.06.2023 00:43:43
*/
#include<bits/stdc++.h>
using namespace std;
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];
}
auto query = [&](int u,int v){
return pref[v + 1] - pref[u];
};
vector<vector<vector<long long>>>dp(n + 1,vector<vector<long long>>(k + 1,vector<long long>(2,-1)));
for (int i = 0;i<n;++i){
dp[i][0][0] = 0;
dp[i][0][1] = -1;
}
for (int i = 1;i<=k;++i){
for (int j = 1;j<n;++j){
for (int p = 0;p<j;++p){
if (dp[j][i][0] < dp[p][i - 1][0] + query(p,j - 1) * query(j,n - 1)){
dp[j][i][0] = dp[p][i - 1][0] + query(p,j - 1) * query(j,n - 1);
dp[j][i][1] = p;
}
}
}
}
long long ans = -1;
int v = -1;
for (int i = 1;i<n;++i){
if (dp[i][k][0] > ans){
ans = dp[i][k][0];
v = i;
}
}
cout<<ans<<'\n';
vector<int>pos;
for (int i = 0;i<k;++i){
pos.push_back(v);
v = dp[v][k - i][1];
}
reverse(pos.begin(),pos.end());
for (auto x:pos)cout<<x<<" ";
cout<<'\n';
return 0;
}
