#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = INT_MAX / 2;
const int MAXN = 3e5 + 5;
int n, k;
ll arr[MAXN], dp[MAXN][2];
int cnt[MAXN][2];
ll answer;
bool eval(ll c)
{
dp[0][1] = -INF;
for (int i = 1; i <= n; i++)
{
if (dp[i - 1][0] >= dp[i - 1][1])
{
dp[i][0] = dp[i - 1][0];
cnt[i][0] = cnt[i - 1][0];
}
else
{
dp[i][0] = dp[i - 1][1];
cnt[i][0] = cnt[i - 1][1];
}
if (dp[i - 1][0] - c >= dp[i - 1][1])
{
dp[i][1] = arr[i] + dp[i - 1][0] - c;
cnt[i][1] = cnt[i - 1][0] + 1;
}
else
{
dp[i][1] = arr[i] + dp[i - 1][1];
cnt[i][1] = cnt[i - 1][1];
}
}
ll optv = LLONG_MIN;
int optx = INT_MIN;
for (int i = 0; i <= n; i++)
for (int ii = 0; ii < 2; ii++)
{
ll nv = dp[i][ii] + c * cnt[i][ii];
int nx = cnt[i][ii];
if (nv > optv)
{
optv = nv;
optx = nx;
}
if (nv == optv)
optx = max(optx, nx);
}
if (optx <= k)
answer = max(answer, optv);
return optx <= k;
}
void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> arr[i];
ll lo = 0, hi = INF;
while (lo <= hi)
{
ll mi = lo + (hi - lo) / 2;
if (eval(mi))
hi = mi - 1;
else
lo = mi + 1;
}
cout << answer << '\n';
}
int main()
{
// ios_base::sync_with_stdio(false), cin.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
