#include <bits/stdc++.h>
#define int long long
using namespace std;
using ii = pair<int,int>;
signed main() {
int n,splits;
cin >> n >> splits;
vector<vector<int>> dp(n, vector<int>(splits+2));
vector<vector<int>> pos(n, vector<int>(splits+2));
vector<int> xs(n);
vector<int> prefix(n);
for (int i = 0ll ; i < n; ++i) {
cin >> xs[i];
prefix[i] = prefix[max(i-1,0ll)] + xs[i];
}
for (int i = 0ll; i < n-1; ++i) {
dp[i][1] = (prefix[n-1] - prefix[i]) * prefix[i];
}
for (int k = 2; k <= splits+1; ++k) {
for (int i = 0ll; i < n; ++ i) {
for (int l = 0ll; l < i; ++l) {
int v = dp[l][k-1] + (prefix[i] - prefix[l])*(prefix[n-1]-prefix[i]);
if (v >= dp[i][k]) {
dp[i][k] = v;
pos[i][k] = l;
}
}
}
}
cout << dp[n-1][splits+1] << '\n';
int cur = n-1;
vector<int> path;
for (int k = splits; k > 0ll; k--) {
for (int l = cur-1; l >= 0ll; --l) {
if (dp[l][k] + (prefix[cur] - prefix[l])*(prefix[n-1]-prefix[cur]) == dp[cur][k+1]) {
path.push_back(l+1);
cur = l;
break;
}
}
}
for(int i = path.size()-1; i >= 0ll; --i) {
cout << path[i] << ' ';
}
cout << '\n';
}
