#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define MAXM 201
#define int long long
const int INF = LLONG_MAX;
struct LiChaoTree {
struct Line {
int m, b;
Line(int _m = 0, int _b = -INF) : m(_m), b(_b) {}
int eval(int x) { return m * x + b; }
};
vector<Line> tree;
int minX, maxX, sz;
LiChaoTree(int _minX, int _maxX) : minX(_minX), maxX(_maxX) {
sz = 1;
while (sz < (maxX - minX + 1)) sz *= 2;
tree.assign(2 * sz, Line());
}
void addLine(Line newLine, int node = 1, int l = 0, int r = -1) {
if (r == -1) r = sz - 1;
int mid = (l + r) / 2;
bool leftBetter = newLine.eval(l + minX) > tree[node].eval(l + minX);
bool midBetter = newLine.eval(mid + minX) > tree[node].eval(mid + minX);
if (midBetter) swap(tree[node], newLine);
if (l == r) return;
if (leftBetter != midBetter) addLine(newLine, 2 * node, l, mid);
else addLine(newLine, 2 * node + 1, mid + 1, r);
}
int getMax(int x) {
int pos = x - minX;
int node = 1, l = 0, r = sz - 1;
int best = -INF;
while (true) {
best = max(best, tree[node].eval(x));
if (l == r) break;
int mid = (l + r) / 2;
if (pos <= mid) {
node = 2 * node;
r = mid;
} else {
node = 2 * node + 1;
l = mid + 1;
}
}
return best;
}
};
int n, k;
int pref[MAXN], dp[2][MAXN];
vector<int> where[MAXM];
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
pref[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> pref[i];
pref[i] += pref[i - 1];
}
for (int i = 1; i < n; i++)
dp[0][i] = pref[i] * (pref[n] - pref[i]);
for (int i = 0; i <= k; i++) where[i].resize(n, -1);
for (int br = 2; br <= k; br++) {
LiChaoTree tree(0, MAXN);
for (int pos = br; pos < n; pos++) {
tree.addLine({pref[pos - 1], dp[0][pos - 1] - pref[pos - 1] * pref[n]});
dp[1][pos] = pref[pos] * (pref[n] - pref[pos]) + tree.getMax(pref[pos]);
}
for (int pos = br; pos < n; pos++)
dp[0][pos] = dp[1][pos];
}
int maks = dp[0][k], pos = k;
for (int i = k + 1; i < n; i++) {
if (dp[0][i] > maks) {
maks = dp[0][i];
pos = i;
}
}
cout << maks << endl;
return 0;
}
