/*
* 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<pair<int,int>>>child(n,vector<pair<int,int>>(n));;
vector<vector<vector<long long>>>dp(n,vector<vector<long long>>(n,vector<long long>(k,-1)));
function<long long(int,int,int)>solve = [&](int u,int v,int p){
if (p == k){
return 0LL;
}
if (dp[u][v][p] != -1){
return dp[u][v][p];
}
long long ans = -1;
long long p1 = 0,p2 = 0;
for (int i = u;i<=v;++i){
if (i + 1 < v)
p1 = (solve(i + 1,v,p + 1) + query(u,i) * query(i + 1,v));
if (i + 1 < v){
p2 = (solve(u,i,p + 1) + query(u,i) * query(i + 1,v));
}
if (max(p1,p2) > ans){
ans = max(p1,p2);
child[u][v] = {i,0};
if (p2 > p1){
child[u][v] = {i,1};
}
}
}
return dp[u][v][p] = ans;
};
vector<int>pos;
int l = 0,r = n - 1;
cout<<solve(0,n - 1,0)<<'\n';
for (int i = 0;i<k;++i){
pos.push_back(child[l][r].first);
if (child[l][r].second == 0){
l = child[l][r].first;
}
else{
r = child[l][r].first;
}
}
for (auto x:pos)cout<<x + 1<<" ";
cout<<'\n';
return 0;
}
