#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1e5 + 5;
ll n, k;
ll A[MAXN];
ll P[MAXN];
ll poprz[MAXN];
ll curr[MAXN];
int powrot[MAXN][201];
const ll MAXLL = 1e18;
struct Node{
pair<ll,ll> F;
int ind;
Node *l, *r;
Node(ll a, ll b, ll c) : F({a,b}), ind(c), l(nullptr), r(nullptr) {}
Node(Node *ll, Node *rr) : l(ll), r(rr) {}
};
ll base = 1 << 30;
Node *roots[MAXN];
bool mniejsza(pair<ll,ll> f1, pair<ll,ll> f2, ll x){
if(f1.first * x + f1.second < f2.first * x + f2.second) return true;
return false;
}
void dodajprosta(Node *curr, ll akt_a, ll akt_b, pair<ll,ll> nowa, int ind){
int mid = (akt_a + akt_b) / 2;
bool czy = mniejsza(nowa, curr->F, mid);
bool lewo = mniejsza(nowa, curr->F, akt_a);
if(czy){
swap(curr->F, nowa);
swap(curr->ind, ind);
}
if(akt_a == akt_b) return;
if(czy != lewo){
if(curr->l == nullptr) curr->l = new Node(0, MAXLL, -1);
dodajprosta(curr->l, akt_a, mid, nowa, ind);
}
else{
if(curr->r == nullptr) curr->r = new Node(0, MAXLL, -1);
dodajprosta(curr->r, mid + 1, akt_b, nowa, ind);
}
return;
}
void usun(Node *x){
if(x->l) usun(x->l);
if(x->r) usun(x->r);
delete(x);
return;
}
pair<pair<ll,ll>, int> minval(Node *curr, ll akt_a, ll akt_b, ll gdzie){
if(akt_a == akt_b) return {curr->F, curr->ind};
int mid = (akt_a + akt_b) / 2;
if(gdzie <= mid){
if(curr->l == nullptr) curr->l = new Node(0, MAXLL, -1);
auto f2 = minval(curr->l, akt_a, mid, gdzie);
if(mniejsza(curr->F, f2.first, gdzie)){
return {curr->F, curr->ind};
}
else{
return f2;
}
}
else{
if(curr->r == nullptr) curr->r = new Node(0, MAXLL, -1);
auto f2 = minval(curr->r, mid + 1, akt_b, gdzie);
if(mniejsza(curr->F, f2.first, gdzie)){
return {curr->F, curr->ind};
}
else{
return f2;
}
}
}
int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
cin >> n >> k;
for(ll i = 1; i <= n; ++i){
cin >> A[i];
P[i] = P[i - 1] + A[i];
}
for(int i = 1; i <= n; ++i){
poprz[i] = MAXLL;
powrot[i][0] = -1;
powrot[i][0] = -1;
}
powrot[0][0] = -1;
for(ll i = 1; i <= k+1; ++i){
roots[0] = new Node(0, MAXLL, -1);
//cout << "#\n";
for(ll j = i; j <= n; ++j){
//cout << "dodaj ind: " << j-1 << " a: " << -2*P[j-1] << " b: " << P[j-1]*P[j-1] << " + " << poprz[j-1] << "\n";
dodajprosta(roots[0], 0, base - 1, {-2*P[j-1], P[j-1]*P[j-1] + poprz[j-1]}, j-1);
auto u = minval(roots[0], 0, base -1, P[j]);
//cout << u.first << " " << u.second << " u\n";
//cout << P[j] << " Pj\n";
curr[j] = P[j] * P[j] + P[j] * u.first.first + u.first.second;
//cout << i << " " << j << " " << u.second << " ustaw pow\n";
powrot[j][i] = u.second;
if(i == 1) continue;
//cout << P[j] << " Pj\n";
//cout << u.second << " powrot\n";
//cout << j << " " << i << " " << curr[j] << "\n";
}
//cout << "\n";
//cout << "#\n";
for(ll j = n; j > i-1; --j){
//cout << "i: " << i << " j: " << j << " " << curr[j] << " DP\n";
poprz[j] = curr[j];
curr[j] = 0;
}
//cout << "\n";
poprz[i-1] = MAXLL;
for(int j = 0; j < i; ++j){
powrot[j][i] = -1;
}
usun(roots[0]);
}
cout << (P[n] * P[n] - poprz[n]) / 2 << "\n";
vector<ll> ans;
ll curr = n;
ll ind = k+1;
while(powrot[curr][ind] != 0){
//cout << curr << " " << ind << " " << powrot[curr][ind] << " pow\n";
ans.push_back(powrot[curr][ind]);
curr = powrot[curr][ind];
ind--;
}
reverse(ans.begin(),ans.end());
// for(auto u : ans){
// cout << u << " ";
// }
// cout << "\n";
return 0;
}
