// https://oj.uz/problem/view/NOI19_feast
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using LL=long long;
using LD=long double;
#define FOR(i,l,r) for(auto i=(l);i<=(r);++i)
#define ROF(i,l,r) for(auto i=(l);i>=(r);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ITF(e,c) for(auto&e:(c))
#define ssize(x) int(x.size())
#ifdef DEBUG
auto operator<<(auto&o,auto p)->decltype(p.first,o){return o<<'('<<p.first<<", "<<p.second<<')';}
auto operator<<(auto&o,auto&x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
int N,K;
vector<int> A;
// calculates dp for λ
pair<LL,int> calc(LL lambda) {
static array<array<pair<LL,int>,2>,2> dp;
dp[0][0] = {0,0}, dp[0][1] = {A[0] - lambda,1};
FOR(i,1,N-1) {
// skip
dp[1][0] = max(dp[0][0], dp[0][1]);
// take
dp[1][1] = max(
pair{dp[0][0].first + A[i] - lambda, dp[0][0].second + 1},
pair{dp[0][1].first + A[i], dp[0][1].second}
);
debug(lambda,i,dp[1]);
// next
swap(dp[0],dp[1]);
}
return max(dp[0][0], dp[0][1]);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
/// input
{
cin >> N >> K;
A.resize(N);
ITF(e,A) cin >> e;
}
/// algo
LL aL;
{
// #warning change this bitch
LL low = 0, high = 1e18, mid;
while(low < high) {
mid = (low + high + 1) / 2;
auto [v,c] = calc(mid);
debug(low,mid,high,v,c);
if (c < K) high = mid - 1;
else low = mid;
}
aL = low;
debug(aL);
}
/// output
{
cout << calc(aL).first + K*aL << endl;
}
return 0;
}
