#include<bits/stdc++.h>
using namespace std;
vector<long long>pref, v;
int n, k;
long long cost(int i, int j){
long long L = pref[j] - pref[i - 1], R = pref[n] - pref[j];
return L * R;
}
long long rec(int l, int k){
long long res = 0;
if(l > n)return -1e18;
if(l == n || k == 0)return 0;
for(int i = l;i <= n;++i){
res = max(res, cost(l, i) + rec(i + 1, k - 1));
}
return res;
}
int main()
{
cin >> n >> k;
pref.resize(n + 1);
v.resize(n + 1);
for(int i = 1;i <= n;++i){
cin >> v[i];
pref[i] = pref[i - 1] + v[i];
}
vector<vector<long long>>dp(k + 1, vector<long long>(n + 1, -1e18));
vector<vector<pair<int, int>>>par(k + 1, vector<pair<int, int>>(n + 1, {-1, -1}));
for(int i = 1;i <= n;++i)dp[0][i] = 0;
for(int i = 1;i <= k;++i)dp[k][n] = 0;
for(int K = 1;K <= k;++K){
for(int i = n;i >= 1;--i){
for(int j = i;j < n;++j){
long long num = cost(i, j) + dp[K - 1][j + 1];
if(dp[K][i] < num){
dp[K][i] = num;
par[K][i] = {K - 1, j + 1};
}
// cout << "dp[" << K << "][" << i << "]=" << dp[K][i] << ": {" << par[K][i].first << ", " << par[K][i].second << "}\n";
}
}
}
long long mx = -1e18;
pair<int, int>num;
for(int i = 1;i <= n;++i){
if(mx < dp[k][i]){
mx = dp[k][i];
num = {k, i};
}
}
vector<int>ans;
while(num.first > 0){
ans.push_back(num.second);
num = par[num.first][num.second];
}
cout << mx << '\n';
for(int i : ans)cout << i << " ";
// cout << mx << '\n' << rec(1, k);
}
