#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
constexpr i64 inf = 1ll << 60;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
template <typename T> bool chmax(T &a, const T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
int main() {
int N, K;
cin >> N >> K;
++K;
vector<i64> A(N);
for (auto &e : A) cin >> e;
vector<i64> R(N + 1);
REP(i, N) R[i + 1] = R[i] + A[i];
auto calc_sum = [&R](int l, int r) { return R[r] - R[l]; };
vector dp(N + 1, vector(K + 1, (i64)-inf));
auto db = dp;
REP(i, N) {
REP3(j, i + 1, N + 1) {
REP(k, K) if (chmax(dp[j][k + 1], dp[i][k] + calc_sum(i, j) * calc_sum(j, N))) db[j][k + 1] = i;
}
}
cout << dp[N][K] << endl;
int now = N;
vector<int> data;
REP(i, K - 1) {
data.push_back(db[now][K - i]);
now = db[now][K - i];
}
reverse(data.begin(), data.end());
REP(i, K - 1) cout << data[i] << (i == K - 1 ? '\n' : ' ');
}
