#include <bits/stdc++.h>
using namespace std;
template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}
#define all(a) a.begin(), a.end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double db;
const int MAX_N = 3e5 + 5;
const db inf = 3e14;
const db eps = 1e-3;
int n, k;
int a[MAX_N];
pair<db, int> dp[2][2];
bool curr, nxt;
int check(db lamda) {
curr = 0, nxt = 1;
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
dp[i][j] = {-inf, -inf};
}
}
dp[curr][0] = {0, 0};
for (int i = 0; i < n; i++, swap(curr, nxt)) {
// 0
maximize(dp[nxt][0], dp[curr][0]);
maximize(dp[nxt][1], pair<db, int>(dp[curr][0].fi - lamda + (db) a[i + 1], dp[curr][0].se + 1));
// 1
maximize(dp[nxt][1], pair<db, int>(dp[curr][1].fi + (db) a[i + 1], dp[curr][1].se));
maximize(dp[nxt][0], dp[curr][1]);
for (int j = 0; j <= 1; j++) {
dp[curr][j] = {-inf, -inf};
}
}
return max(dp[curr][1], dp[curr][0]).se;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("FEAS.inp", "r")) {
freopen("FEAS.inp", "r", stdin);
freopen("FEAS.out", "w", stdout);
}
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
db low = 0, high = inf;
while (low + eps < high) {
db mid = (low + high) / 2;
if (check(mid) >= k) {
low = mid;
}
else {
high = mid;
}
}
db ans = low;
check(ans);
cout << (ll) round(max(dp[curr][0], dp[curr][1]).fi + ans * k);
return 0;
}
/*
Saturday, 16 December 2023
14:53:03
*/
