#include <bits/stdc++.h>
// author: aykhn
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define mpr make_pair
#define eb emplace_back
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define ins insert
#define int ll
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount
const int MXN = 1e3 + 5;
int n, k;
int a[MXN], pref[MXN];
int dp[MXN][MXN];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
cin >> n >> k;
k++;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) dp[i][1] = pref[i] * (pref[n] - pref[i]);
for (int i = 1; i <= n; i++)
{
for (int j = i - 1; j >= 1; j--)
{
for (int k1 = 2; k1 <= k; k1++)
{
dp[i][k1] = max(dp[i][k1], pref[j] * (pref[i] - pref[n]) + dp[j][k1 - 1] + pref[i] * pref[n] - pref[i] * pref[i]);
}
}
for (int k1 = 2; k1 <= k; k1++) assert(dp[i][k1] >= dp[i - 1][k1]);
}
cout << dp[n][k] << '\n';
int x = n;
int y = k;
vector<int> v;
while (y > 1)
{
for (int i = x - 1; i >= 1; i--)
{
if (dp[x][y] == dp[i][y - 1] + (pref[x] - pref[i]) * (pref[n] - pref[x]))
{
x = i;
break;
}
}
y--;
v.pb(x);
}
sort(all(v));
for (int x : v) cout << x << ' ';
cout << '\n';
}
