#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Reduced to 10005 to fit within the 128MB limit for long long
const int nx = 10005;
int n, k;
ll dp[nx][205]; // Changed to long long
int choice[nx][205];
ll a[nx]; // Changed to long long to prevent multiplication overflow
ll solve(int idx, int rem) {
if (idx > n) return 0;
if (rem < 0) return 0;
if (dp[idx][rem] != -1) return dp[idx][rem];
if (rem == 0) {
choice[idx][rem] = n;
return dp[idx][rem] = 0;
}
int select = n;
ll mx = 0;
if (rem >= 1) {
for (int i = idx; i + 1 <= n; i++) {
// Because 'a' is now ll, this multiplication won't overflow
ll val = solve(i + 1, rem - 1) + (a[n] - a[i]) * (a[i] - a[idx - 1]);
if (val > mx) {
mx = val;
select = i;
}
}
}
choice[idx][rem] = select;
return dp[idx][rem] = mx;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] += a[i - 1];
}
memset(dp, -1, sizeof dp);
dp[1][k] = solve(1, k);
cout << dp[1][k] << "\n";
int i = choice[1][k--];
if (i != n) cout << i;
while (i != n) {
i++;
i = choice[i][k--];
if (i == n) break;
cout << " " << i;
}
}
