#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define in insert
#define lb lower_bound
#define F first
#define S second
#define sz size()
#define int long long
#define all(v) v.begin(),v.end()
#define FOR1(x, n) for(int j = x; j <= n; j ++)
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)
#define FORR(x, n, m, d) for(int x = n; x >= m; x -= d)
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);
const int N = 1e5+5;
int a[N], b[N], pref[N];
pair<int, int> dp[100005][205];
int n,m,k,sum=0,x,y, ans, r, cnt, l, mod = 1e9+7, inf = -1e18;
string s, str;
bool used[N];
struct kxt{
int l, r, b, k, ind;
};
struct obtain{
int k, b, ind;
};
vector<kxt>v;
void add(int b, int k, int po){
while(v.sz){
kxt i = *v.rbegin();
if(k == i.k){
if(b >= i.b)v.pop_back();
else{
return;
}
}
else{
int pl = ( i.b - b ) / ( k - i.k );
if(pl < 0){
v.pop_back();
}
else{
if( pl >= i.r)v.pop_back();
else{
v.pop_back();
v.pb({i.l, pl, i.b, i.k, i.ind});
v.pb({pl+1, inf*-1, b, k, po});
return;
}
}
}
}
v.pb({inf, inf*-1, b, k, po});
}
obtain get( int pos, int l = 0, int r = v.sz-1){
while(l <= r){
int md = (l + r) >> 1;
if(v[md].l <= pos)l = md + 1;
else r = md - 1;
}
return {v[r].k, v[r].b, v[r].ind};
}
void solve(){
cin >> n >> m;
FOR(i, 1, n, 1)cin >> a[i], pref[i] = pref[i-1] + a[i];
x = y = 0;
int io;
ans = -1e18;
FOR(i, 1, n-1, 1){
dp[i][1].F = (pref[n] - pref[i]) * pref[i];
if(ans < dp[i][1].F)ans = max(ans, dp[i][1].F), io = i;
}
FOR(i, 2, m, 1){
FOR(j, i-1, i-1, 1)add(dp[j][i-1].F, pref[j], j);
FOR(j, i, n-1, 1){
obtain ok = get(pref[j]-pref[n]);
cnt = ok.b + ok.k * (pref[j]-pref[n]) + pref[j] * (pref[n] - pref[j]);
// pref[n] * pref[j] - pref[n] * pref[ok] - pref[j] * pref[j] + pref[j] * pref[ok]
// - pref[n] * pref[ok] + pref[j] * pref[ok]
// pref[ok] * (pref[j] - pref[n])
dp[j][i].F = cnt, dp[j][i].S = ok.ind;
if(ans <= dp[j][i].F)ans = dp[j][i].F, io = j;
add(dp[j][i-1].F, pref[j], j);
}
v.clear();
}
x = m;
cout << ans << '\n';
vector<int>lp;
while(x > 0)lp.pb(io), io = dp[io][x].S, x --;
FORR(i, lp.sz-1, 0, 1)cout << lp[i] << ' ';
}
signed main(){
nikita
int tt = 1;
if(!tt)cin >> tt;
FOR(i, 1, tt, 1)solve();
}
