#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// ---------- Global data ----------
const ll NEG = LLONG_MIN / 4;
int n, k;
vector<ll> a, s;
vector<ll> dp_prev, dp_cur;
void solve(int l, int r, int optL, int optR) {
if (l > r) return;
int mid = (l + r) >> 1;
pair<ll,int> best = {NEG, -1};
for (int j = optL; j <= min(mid-1, optR); j++) {
ll val = dp_prev[j] + s[j] * (s[mid] - s[j]);
if (val > best.first) best = {val, j};
}
dp_cur[mid] = best.first;
int opt = best.second;
solve(l, mid-1, optL, opt);
solve(mid+1, r, opt, optR);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
a.assign(n+1, 0);
s.assign(n+1, 0);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) s[i] = s[i-1] + a[i];
dp_prev.assign(n+1, 0);
dp_cur.assign(n+1, 0);
for (int t = 1; t <= k; t++) {
solve(1, n, 0, n-1);
dp_prev = dp_cur;
}
cout << dp_prev[n] << "\n";
return 0;
}
