#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int inf = 1e16;
const int K = 205;
int dp[N][K], pref[N], a[N], n, pos[N][K], k;
void Solve(int l, int r, int low, int high, int x) {
if(l > r) return;
int mid = l + r >> 1;
int opt = low, rez = dp[low - 1][x - 1] + pref[low - 1] * (pref[mid] - pref[low - 1]);
for(int i = low + 1; i <= min(mid, high); i++) {
if(rez < dp[i - 1][x - 1] + (pref[mid] - pref[i - 1]) * pref[i - 1]) {
rez = dp[i - 1][x - 1] + (pref[mid] - pref[i - 1]) * pref[i - 1];
opt = i;
}
}
pos[mid][x] = opt;
dp[mid][x] = rez;
Solve(l, mid - 1, low, opt, x);
Solve(mid + 1, r, opt, high, x);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
k++;
for(int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
dp[i][0] = -inf;
}
for(int i = 1; i <= k; i++) Solve(1, n, 1, n, i);
cout << dp[n][k] << "\n";
vector<int> ans;
int index = n, kk = k;
while(index > 0) {
if(index != n) ans.push_back(index);
kk--;
index = pos[index][kk];
}
reverse(ans.begin(), ans.end());
for(int i : ans) cout << i << " ";
}
