#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
using ll = long long;
const int MAXN = 1e5;
const int MAXK = 200;
ll dp[MAXN][MAXK];
ll arr[MAXN];
ll transition[MAXN][MAXK];
int nb_elem;
ll calc_dp(int cur, int nb_split)
{
if (dp[cur][nb_split] != -1)
return dp[cur][nb_split];
if (nb_split == 0)
return 0;
if (cur==nb_elem)
return -2e18;
ll cumu_sum_lft(0), cumu_sum_rgt(0);
for (int i(cur); i < nb_elem; ++i)
cumu_sum_rgt += arr[i];
for (int nxt(cur); nxt < nb_elem; ++nxt)
{
cumu_sum_lft += arr[nxt];
cumu_sum_rgt -= arr[nxt];
ll score = cumu_sum_rgt * cumu_sum_lft + calc_dp(nxt+1, nb_split-1);
if (score > dp[cur][nb_split])
{
dp[cur][nb_split] = score;
transition[cur][nb_split] = nxt;
}
}
return dp[cur][nb_split];
}
int main(void)
{
int nb_split;
cin >> nb_elem >> nb_split;
for (int i(0); i < nb_elem; ++i)
cin >> arr[i];
for (int i(0); i < nb_elem; ++i)
for (int j(0); j <= nb_split; ++j)
dp[i][j] = -1;
cout << calc_dp(0, nb_split) << endl;
int cur(0);
for (int i(0); i < nb_split; ++i)
{
cur = transition[cur][nb_split-i] + 1;
cout << cur << ' ';
}
cout << endl;
}
