#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1e9 + 7;
//const ll Inf = 2242545357980376863LL;
const ll Log = 20;
//const ll N = 1ll << Log;
const int Maxn = 1e5 + 10;
//const int Base = 101;
typedef pair<ll, ll> Line;
typedef pair<pair<ll, Line>, int> Ty;
vector<Ty> L;
ll INF = 4e18;
inline ll Intersection(Line X, Line Y){
if (X.first == Y.first && X.second >= Y.second)
return (-INF);
if (X.first == Y.first)
return (INF);
return ((Y.second - X.second) / (X.first - Y.first)) + ((Y.second - X.second) % (X.first - Y.first) > 0);
}
inline void Add(Line X, ll idx){
while(!L.empty() && Intersection(L.back().F.S, X) <= L.back().F.F)
L.pop_back();
L.pb({{(L.empty() ? -INF : Intersection(L.back().F.S, X)), X}, idx});
}
inline pll GetMin(ll X){
auto it = --upper_bound(all(L), Ty({X, {INF, INF}}, INF));// it --;
return pll((X * it->F.S.F + it->F.S.S), it -> S);
}
int a[Maxn];//, mk[Maxn];
ll ps[Maxn];//, sf[Maxn];
ll dp[2][Maxn];
int par[203][Maxn];
vector<ll> A;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
L.reserve(Maxn);
//debug((-3) / 2);
ll n, k;
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> a[i];
ps[0] = 0;
for(int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i - 1];
for(int i = 0; i <= n; i++) dp[0][i] = ps[i] * ps[i];
pll res;
int jj;
for(int j = 1; j <= k; j++){
L.clear();
jj = j & 1;
dp[jj][0] = 0;
for(int i = 1; i <= n; i++){
Add( pll(-2LL * ps[i - 1], dp[jj ^ 1][i - 1] + ps[i - 1]*ps[i - 1] ), i - 1);
res = GetMin(ps[i]);
dp[jj][i] = res.F + ps[i]*ps[i];
par[j][i] = res.S;
}
}
cout << ((ps[n] * ps[n]) - dp[k&1][n]) / 2LL << '\n';
ll nw = n;
for(int i = 0; i < k; i++){
nw = par[k - i][nw];
A.pb(nw);
}
reverse(all(A));
for(auto x : A) cout << x << ' ';
cout << '\n';
return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/
