#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
vector<ll> vec;
vector<vector<pair<ll, ll>>> memo;
ll amount, lambda;
pair<ll, ll> dp(ll i, bool open) // profit, segments
{
if(i == amount-1) return open ? make_pair(vec[i] - lambda, 1ll) : make_pair(0ll, 0ll);
if(memo[i][open].second != -1) return memo[i][open];
pair<ll, ll> best = {LLONG_MIN, LLONG_MIN};
if(!open) best = max(dp(i+1, 1), dp(i+1, 0));
else best = max(pll{dp(i+1, 1).first + vec[i], dp(i+1, 1).second},
pll{dp(i+1, 0).first + vec[i] - lambda, dp(i+1, 0).second+1});
return memo[i][open] = best;
}
int main()
{
ll seg, s = 0;
scanf("%lld %lld", &amount, &seg);
vec.resize(amount);
for(ll i = 0; i < amount; i++)
{
scanf("%lld", &vec[i]);
s += max(vec[i], 0ll);
}
ll l = 0, r = s;
while(l <= r)
{
lambda = (l + r) / 2;
memo.assign(amount, vector<pll>(2, {-1, -1}));
auto res = max(dp(0, 0), dp(0, 1));
if(res.second > seg)
{
l = lambda+1;
}
else if(res.second < seg)
{
r = lambda-1;
}
else
{
l = lambda;
r = lambda-1;
}
}
lambda = l;
memo.assign(amount, vector<pll>(2, {-1, -1}));
auto res = max(dp(0, 0), dp(0, 1));
// cout << res.first << " " << lambda << "\n";
printf("%lld\n", res.first + res.second * lambda);
}
