#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long double db;
typedef pair<db, int> PLI;
const int INF = 1e9 + 47;
PLI f(VI& a, db lambda)
{
int n = SZ(a);
PLI dp0 = {0, 0};
PLI dp1 = {-47ll * INF, 0};
FOR (i, 0, n)
{
PLI ndp0 = max(dp0, dp1);
PLI ndp1 = max(PLI(dp0.F + a[i] - lambda, dp0.S + 1), PLI(dp1.F + a[i], dp1.S));
dp0 = ndp0;
dp1 = ndp1;
//cerr << i << ' ' << dp0.F << ' ' << dp0.S << ' ' << dp1.F << ' ' << dp1.S << '\n';
}
return max(dp0, dp1);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
VI a(n);
FOR (i, 0, n)
cin >> a[i];
db l = -1, r = INF;
FOR (i, 0, 74)
{
db m = (l + r) / 2;
auto [val, cnt] = f(a, m);
if (cnt > k)
l = m;
else
r = m;
}
//cerr << r << '\n';
auto [val, cnt] = f(a, r);
cout << LL(val + cnt * r) << '\n';
return 0;
}
