#include <bits/stdc++.h> // +
using namespace std; // +++
#define inf 1e18 // +
#define int long long
#define all(a) a.begin(), a.end()
void files() {
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
// #endif
}
int const N = 3e5 + 5;
pair<int, int> dp[N][2];
int vis[N][2], id;
int n, k, a[N];
int lamda;
pair<int, int> rec(int i, bool lst) {
if (i == n) return {0, 0};
auto &ret = dp[i][lst];
if (vis[i][lst] == id) return ret;
vis[i][lst] = id;
auto leave = rec(i + 1, 0);
auto take = rec(i + 1, 1);
take.first += a[i];
if (!lst) {
take.first -= lamda;
take.second--;
}
return ret = max(leave, take);
}
void solve() {
cin >> n >> k;
for (int i = 0; i < n; ++i) cin >> a[i];
// st = 0 "AT MOST K" (empty allowed).
// st = -1e15 "EXACTLY K" (must force bad choices).
// en = 1e15 Always. It forces the DP to pick 0 items.
int st = 0, en = 1e15, md;
__int128_t ans = 0;
while (st <= en) {
md = st + (en - st) / 2;
lamda = md;
++id;
auto [cur_ans, cnt] = rec(0, 0);
int used = -cnt; // cnt that you take (neg in dp)
if (used > k) {
// We used too many items. The penalty is too weak.
st = md + 1;
} else {
// We used <= k items. This is a valid configuration!
// Refund the penalty for exactly K items to get the true score.
ans = cur_ans + (__int128_t)md * k;
// Try to find a smaller valid penalty to handle collinear points
en = md - 1;
}
}
cout << (int)ans << '\n';
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), files();
int tc = 1;
// cin >> tc;
while (tc--)
solve();
}
