#include <iostream>
// #include <utility>
#include <vector>
#define V std::vector
const long long NEGINFINITY = -100000000000000ll;
int main() {
int n, k;
std::cin >> n >> k;
std::vector<int> v(n);
for (int i = 0; i < n; ++i) std::cin >> v[i];
std::vector<long long> p(n + 1);
for (int i = 1; i <= n; ++i) p[i] = p[i - 1] + v[i - 1];
// dp[i][kk][prev] = max score in prefix i with kk more splits, the last of which is at prev
V<V<V<long long>>> dp(n, V<V<long long>>(k + 1));
V<V<int>> bestfrom(n, V<int>(k + 1));
dp[0][0].push_back(0);
bestfrom[0][0] = -1;
for (int kk = 1; kk <= k; ++kk) dp[0][kk].push_back(NEGINFINITY);
for (int i = 1; i < n; ++i) {
for (int kk = 0; kk <= std::min(k, i); ++kk) dp[i][kk].resize(i + 1);
for (int prev = 0; prev < i; ++prev) {
for (int kk = 0; kk <= std::min(k, i); ++kk) {
if (kk != i)
dp[i][kk][prev] = dp[i - 1][kk][prev];
}
}
for (int kk = 0; kk <= std::min(k, i); ++kk) {
if (kk == 0) {
dp[i][kk][i] = NEGINFINITY;
continue;
}
long long max = NEGINFINITY;
for (int prev = 0; prev < i; ++prev) {
long long score = dp[i - 1][kk - 1][prev] + (p[i] - p[prev]) * (p.back() - p[i]);
if (score > max) {
max = score;
bestfrom[i][kk] = prev;
}
}
dp[i][kk][i] = max;
}
}
long long max = 0;
int cur;
for (int prev = 0; prev < n; ++prev) {
if (dp[n - 1][k][prev] > max) {
max = dp[n - 1][k][prev];
cur = prev;
}
}
std::cout << max << '\n';
int kk = k;
while (kk) {
std::cout << cur << " \n"[kk == 1];
cur = bestfrom[cur][kk];
--kk;
}
return 0;
}
