#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long inf = -4e18;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
int n, K;
cin >> n >> K;
vector<int> ar(n + 1), pref(n + 1);
for(int i = 1; i <= n; ++i){
cin >> ar[i];
pref[i] = pref[i - 1] + ar[i];
}
auto query = [&](int l, int r){
if(r < l) return 0LL;
return pref[r] - pref[l - 1];
};
vector<vector<pair<int, int>>> dp(n + 5, vector<pair<int, int>> (K + 5, {inf, 0}));
for (int i = 1; i <= n+1; i++) dp[i][0] = {0, 0};
for (int k = 1; k <= K; k++) {
for (int i = n; i >= 1; i--) {
for (int j = i; j < n; j++) {
dp[i][k] = max(dp[i][k], {query(i,j) * query(j+1,n) + dp[j+1][k-1].first, j});
}
}
}
cout << dp[1][K].first << "\n";
vector<int> cuts;
int i = 1, k = K;
while (k > 0 && i <= n) {
int j = dp[i][k].second;
if (j == -1) break;
cuts.push_back(j);
i = j + 1;
k--;
}
for (int x : cuts) cout << x << " ";
cout << "\n";
return 0;
}
