#include <iostream>
#include <vector>
typedef long long int ll;
using namespace std;
#define dbg(v) cout << #v << " = " << v << "\n";
int main() {
int n, k;
cin >> n >> k;
vector<ll> arr(n);
for (auto &v: arr) cin >> v;
// vector<ll> b(k*2+1);
// for (int i = 0; i < n; i++) {
// ll a;
// cin >> a;
// for (int j = k*2-1; j >= 1; j -= 2) {
// b[j+1] = max(b[j], b[j+1]);
// b[j] = max(b[j], b[j-1]) + a;
// }
// }
// ll r = 0;
// for (ll v: b) r = max(v,r);
ll ah = 1LL << 34;
ll al = 0;
ll r;
while (ah >= al) {
ll am = (ah + al) / 2;
ll pn = 0;
ll pi = -(1LL<<62);
ll scn = 0;
ll sci = 0;
for (auto v: arr) {
if (pi > pn) scn = sci;
pn = max(pi, pn);
if (pn-am > pi) sci = scn+1;
pi = max(pi, pn-am) + v;
}
r = max(pn, pi) + (pn > pi ? scn : sci) * am;
// dbg(am);
// dbg(pn);
// dbg(pi);
// dbg(scn);
// dbg(sci);
if (al == ah) break;
if ((pn > pi ? scn : sci) > k) {
al = am;
if (al == am) al++;
} else {
ah = am;
}
}
cout << r << "\n";
}
