//#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define TASK "QNOI"
#define ll long long
#define f first
#define s second
#define pb push_back
#define For(i,l,r) for (int i=l;i<=r;i++)
#define Fod(i,r,l) for (int i=r;i>=l;i--)
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
typedef pair<int,int> ii;
typedef unsigned long long ull;
const int N = 1000;
const ll oo = 1e15;
ll dp[N + 5][N + 5];
int main () {
faster;
int n, k;
cin >> n >> k;
vector <ll> a(n + 1, 0);
vector <ll> pre(n + 1, 0);
For(i, 1, n) cin >> a[i], pre[i] = pre[i - 1] + a[i];
For(i, 0, N) For(j, 0, N) dp[j][i] = -oo;
dp[0][0] = 0;
For(i, 1, n)
For(j, 1, k) {
For(l, 0, i - 1)
dp[i][j] = max(dp[i][j], dp[l][j - 1] + 1ll * (pre[n] - pre[i]) * (pre[i] - pre[l]));
}
ll ans = 0;
For(i, 1, n) ans = max(ans, dp[i][k]);
cout << ans << endl;
vector <int> res;
int cnt = k - 1;
int tmp = 1;
For(i, 1, n) {
if(dp[i][k] == ans) {
res.pb(i);
tmp = i;
Fod(j, i - 1, 1) {
if(cnt == 0) break;
if(dp[j][cnt] + 1ll * (pre[n] - pre[tmp]) * (pre[tmp] - pre[j]) == ans) {
res.pb(j);
cnt--;
ans = dp[j][cnt + 1];
tmp = j;
}
}
break;
}
}
reverse(res.begin(), res.end());
for(int i : res) cout << i << " ";
}
