#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
const int inf = 1e9;
const ll inf64 = 1e18;
struct output {
ll res;
void print() {
cout << res << "\n";
}
bool operator == (const output& o) const {
return res == o.res;
}
};
struct input {
int n, k;
vector<int> a;
vector<ll> pref;
input() = default;
void read() {
cin >> n >> k;
a.resize(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
}
void print() {
cout << n << " " << k << "\n";
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << "\n";
}
void gen() {
static mt19937 rnd(42);
const int MAXN = 10;
const int MAXX = 10;
n = rnd() % MAXN + 1;
k = rnd() % n + 1;
a.resize(n + 1);
for (int i = 1; i <= n; i++)
a[i] = rnd() % (2 * MAXX + 1) - MAXX;
}
void gen_max_test() {
}
pair<ll, int> check(ll lambda) {
vector<pair<ll, int>> dp(n + 1, make_pair(-inf64, -inf)), pr = dp;
pr[0] = {0, 0};
pair<ll, int> mx = {pr[0].first - pref[0], pr[0].second};
for (int i = 1; i <= n; i++) {
{
pair<ll, int> tmp = {
mx.first + (pref[i]) - lambda,
mx.second + 1
};
dp[i] = max(dp[i], tmp);
}
pr[i] = max(pr[i - 1], dp[i]);
mx = max(mx, make_pair(pr[i].first - pref[i], pr[i].second));
}
pair<ll, int> res = {-inf64, -inf};
for (int i = 1; i <= n; i++)
res = max(res, dp[i]);
return res;
}
output fast() {
pref.assign(n + 1, 0);
for (int i = 1; i <= n; i++)
pref[i] = pref[i - 1] + a[i];
ll bl = 0, br = inf64 / 3, bm;
while (br - bl > 1) {
bm = bl + (br - bl) / 2;
auto tmp = check(bm);
if (tmp.second >= k) bl = bm;
else br = bm;
}
ll res = 0;
auto tmp = check(bl);
res = max(res, tmp.first + 1ll * bl * k);
return output{res};
}
output slow() {
#ifndef DEBUG
throw;
#endif
vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, -inf64));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int c = 0; c <= k; c++) {
dp[i][c] = max(dp[i - 1][c], c ? dp[i][c - 1] : -inf64);
ll sm = 0;
for (int j = i; j >= 1; j--) {
sm += a[j];
dp[i][c] = max(dp[i][c], (c ? dp[j - 1][c - 1] : -inf64) + sm);
}
}
}
return output{dp[n][k]};
}
};
void test_case() {
input in;
in.read();
output res = in.fast();
res.print();
}
void work() {
int t = 1;
while (t--)
test_case();
}
void test() {
for (int t = 1;;t++) {
input in;
in.gen();
input in_fs = in;
input in_sl = in;
output fs = in_fs.fast();
output sl = in_sl.slow();
if (fs == sl) {
cout << "OK" << endl;
fs.print();
cout << "\n=========" << endl;
} else {
cout << "WA " << t << "\n";
cout << "exp\n";
sl.print();
cout << "\n=========\n";
cout << "fnd\n";
fs.print();
cout << "\n=========\n";
in.print();
break;
}
}
}
void max_test() {
input in;
in.gen_max_test();
input in_fs = in;
output fs = in_fs.fast();
fs.print();
}
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
work();
// test();
// max_test();
return 0;
}
