#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
const int maxN = 1e5 + 20;
const int maxK = 2e2 + 20;
int a[maxN];
int pref[maxN];
long long dp[maxN][maxK];
int best[maxN][maxK];
void just_do_it() {
int N, K;
cin >> N >> 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++) {
for (int j = 1; j <= K + 1; j++) {
dp[i][j] = -1;
best[i][j] = -1;
for (int k = i - 1; k >= 0; k--) {
long long cur = dp[k][j - 1] + 1LL * (pref[i] - pref[k]) * (pref[N] - pref[i]);
if (cur > dp[i][j]) {
dp[i][j] = cur;
best[i][j] = k;
}
}
}
}
cout << dp[N][K + 1] << '\n';
int cur = N;
for (int i = K + 1; i >= 2; i--) {
cout << (cur = best[cur][i]) << " ";
}
}
