#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name "sequence"
using namespace std;
const ll maxn = 1e5+5, inf=1e18;
ll n,k,a[maxn],dp[3][maxn],pf[maxn];
int opts[205][maxn];
vector<ll> ans;
ll getCost(ll l, ll r){
return (pf[r] - pf[l-1]) * pf[l-1];
}
void calculate(ll i, ll u, ll v, ll l, ll r,ll ri){
// dp[i][j] = max(dp[i-1][u-1] + c(u,j))
if(l > r || u > v) return;
ll j = (u+v)/2;
// cout << i << ' ' << j << endl;
ll opt = 0;
dp[i][j] = -inf;
for(ll u = l;u<=min(r, j);u++){
ll ndp = dp[i-1][u-1] + getCost(u, j);
if(ndp >= dp[i][j]){
opt = u;
dp[i][j] = ndp;
}
}
opts[ri][j] = opt;
if(u == v) return;
ll mid = (u+v)/2;
calculate(i, u, mid-1, l, opt, ri);
calculate(i, mid+1, v, opt, r, ri);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
if(fopen(__file_name ".in", "r")){
freopen(__file_name ".in","r",stdin);
freopen(__file_name ".out","w",stdout);
}
// code here
cin >> n >> k;
f1(i,n) {
cin >> a[i];
pf[i] = pf[i-1] + a[i];
}
f1(i,k) {
// memset(dp[2], 0x3f, sizeof(dp[2]));
calculate(2, 1, n, 1, n, i);
f1(j,n) dp[1][j] = dp[2][j];
}
cout << dp[1][n];el;
ll cc = n;
for(ll i=k;i>=1;i--){
ans.push_back(opts[i][cc]-1);
cc = opts[i][cc]-1;
}
// ans.pop_back();
if(ans.size() != k) exit(-1);
for(ll ind: ans) cout << ind << ' ';el;
return 0;
}
/*
Code by: Nguyen Viet Trung Nhan
Cau Giay Secondary School
*/
