#include"bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
int dp[10001][201];
int dp2[10001][201];
int best[10001][201];
int best2[10001][201];
signed main() {
int n, k;
cin >> n >> k;
int a[n];
int pref[n];
int suff[n];
for (int i = 0 ; i < n ; i++) {
cin >> a[i];
if (i) pref[i] = pref[i-1];
else pref[i] = 0;
pref[i] += a[i];
}
for (int i = n - 1 ; i >= 0 ;i--) suff[i] = (i < n - 1 ? suff[i + 1] : 0) + a[i];
int mx1 = 0;
for (int j = 0 ; j < k ; j++) {
for (int i = 0 ; i < n ; i++) {
if (j == 0) {
dp[i][j] = 0;
continue;
}
dp[i][j] = -INT_MAX;
for (int l = 0 ; l < i ; l++) {
int prod = pref[l] * (pref[i] - pref[l]);
int v = dp[l][j-1] + prod;
if (j == k - 1) v += (i < n - 1 ? suff[i + 1] : 0) * pref[i];
if (v > dp[i][j]) {
dp[i][j] = v;
best[i][j] = l;
}
}
mx1 = max(mx1, dp[i][j]);
}
}
int mx2 = 0;
for (int j = 0 ; j < k ; j++) {
for (int i = n-1 ; i >= 0 ; i--) {
if (j == 0) {
dp2[i][j] = 0;
continue;
}
dp2[i][j] = -INT_MAX;
for (int l = n-1 ; l > i ; l--) {
int prod = suff[l] * (suff[i] - suff[l]);
int v = dp2[l][j-1] + prod;
if (j == k - 1) v += suff[i] * (i ? pref[i-1] : 0);
if (v > dp2[i][j]) {
dp2[i][j] = v;
best2[i][j] = l;
}
}
mx2 = max(mx2, dp2[i][j]);
}
}
// for (int i = 0 ; i < n ; i++) {
// for (int j = 0 ; j < k ; j++) {
// cout << dp2[i][j] << " ";
// }
// cout << endl;
// }
if (mx2 > mx1) {swap(mx2, mx1);swap(dp, dp2);swap(best, best2);}
int cur = 0;
int kk = k - 1;
for (int i = 0 ; i < n ; i++) {
if (dp[i][kk] == mx1) cur = i;
}
cout << mx1 << "\n";
vector<int> v;
while (kk >= 0) {
v.push_back(cur + 1);
cur = best[cur][kk--];
}
reverse(v.begin(), v.end());
for (int i : v) cout << i << " ";
}
