#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<long long> sum(n);
sum[0] = a[0];
for (int i = 1; i < n; i++) {
sum[i] = a[i] + sum[i - 1];
}
vector<long long> dp(n);
vector<vector<int>> en(k + 1, vector<int>(n, -1));
for (int i = 0; i < n; i++) {
dp[i] = (sum[n - 1] - sum[i]) * (sum[i]);
}
for (int i = 2; i <= k; i++) {
vector<long long> new_dp(n, 0);
for (int j = i - 1; j < n; j++) {
for (int p = i - 2; p < j; p++) {
long long cost = (sum[n - 1] - sum[j]) * (sum[j] - sum[p]);
if (dp[p] + cost > new_dp[j]) {
new_dp[j] = dp[p] + cost;
en[i][j] = p;
assert(n > p && p > en[i - 1][p]);
}
}
}
swap(dp, new_dp);
}
pair<long long, int> p = {-1, -1};
for (int i = 0; i < n; i++) {
p = max(p, {dp[i], i});
}
cout << p.first << '\n';
int ptr = p.second;
for (int i = k; i > 0; i--) {
cout << ptr + 1 << " ";
assert(en[i][ptr] < ptr);
ptr = en[i][ptr];
}
cout << '\n';
return 0;
}
