#include <bits/stdc++.h>
using namespace std;
#define int long long
pair<int, int> lambda_func(int lmb, const vector<int> &base){
vector<vector<pair<int, int>>> dp(base.size(), vector<pair<int, int>> (2, {0, 0}));
dp[0][0] = {0, 0}, dp[0][1] = {base[0] - lmb, 1};
for(int i = 1; i < base.size(); i++){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max( make_pair(dp[i - 1][0].first + base[i] - lmb, dp[i - 1][0].second + 1),
make_pair(dp[i - 1][1].first + base[i], dp[i - 1][1].second));
} return max(dp.back()[0], dp.back()[1]);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n, m; cin >> n >> m;
vector<int> base(n);
for(int & i : base) cin >> i;
int left = 0, right = 1e18;
while(left < right){
int mid = (left + right + 1) / 2;
pair<int, int> res = lambda_func(mid, base);
if(res.second >= m) left = mid;
else right = mid - 1;
} int res = lambda_func(left, base).first + left * m;
cout << res << endl;
}
