#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e4 + 100;
const ll K = 205;
ll n, k, a[N], dp[N][K], par[N][K], suff[N];
int main(){
cin >> n >> k;
k++;
for (ll i = 1; i <= n; i ++)
cin >> a[i];
for (ll i = n; i > 0; i --)
suff[i] = suff[i + 1] + a[i];
for (ll p = 2; p <= k; p ++){
int j = n - p + 2;
for (ll i = n - p + 1; i > 0; i --){
dp[i][p] = dp[j][p - 1] + (suff[i] - suff[j]) * suff[j];
par[i][p] = j;
while (j - 1 > i and (dp[j - 1][p - 1] + (suff[i] - suff[j - 1]) * suff[j - 1]) >= dp[i][p]){
j--;
dp[i][p] = dp[j][p - 1] + (suff[i] - suff[j]) * suff[j];
par[i][p] = j;
// cout << i << " " << p << " -- " << j << endl;
}
// cout << i << " " << p << " goes to " << j << " and val = " << dp[i][p] << endl;
// for (ll j = i + 1; j <= n - p + 2; j ++){
// ll nval = dp[j][p - 1] + (suff[i] - suff[j]) * suff[j];
// // cout << i << " " << p << " goes to " << j << " and val = " << nval << endl;
// if (nval > dp[i][p])
// par[i][p] = j;
// dp[i][p] = max(dp[i][p], nval);
// }
}
}
cout << dp[1][k] << endl;
int cur_i = 1;
int cur_k = k;
while (cur_k > 1){
cout << par[cur_i][cur_k] - 1 << " ";
cur_i = par[cur_i][cur_k];
cur_k--;
}
cout << endl;
}
