#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll k, n;
vector<ll> a;
struct state {
ll ans;
int cnt;
bool operator<(const state &s) const {
return make_pair(ans, cnt) < make_pair(s.ans, s.cnt);
}
state operator+(ll v) const {
return {ans+v, cnt};
}
state operator+(pair<ll, int> v) const {
return {ans+v.first, cnt+v.second};
}
ll comp(ll p) {
return ans + p * cnt;
}
};
state test(ll cost) {
state dp_old[2], dp_new[2];
dp_old[0] = {0, 0};
dp_old[1] = {a[0] - cost, 1};
for (int i = 1; i < n; ++i) {
dp_new[0] = max(dp_old[0], dp_old[1]);
dp_new[1] = max(dp_old[1] + a[i], dp_old[0] + make_pair(a[i] - cost, 1));
swap(dp_old, dp_new);
}
return max(dp_old[0], dp_old[1]);
}
void solve() {
cin >> n >> k;
a.resize(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
ll l = 0, r = 1e14;
ll ans = 0;
int c;
while (r - l > 1) {
ll m = (l + r) / 2;
auto s = test(m);
c = s.cnt;
if (c >= k)
l = m;
else
r = m - 1;
}
ans = max(test(l).comp(l), test(r).comp(r));
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
// ll t;
// cin >> t;
//
// while (t--) solve();
return 0;
}
