#include <bits/stdc++.h> using namespace std; typedef long long llong; const int MAXN = 3e5 + 10; llong n, k; llong a[MAXN]; pair < llong, llong > dp[MAXN][2]; void read() { cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> a[i]; } } pair < llong, llong > check(llong x) { dp[1][0] = {0, 0}; dp[1][1] = {a[1] - x, 1}; for(int i = 2; i <= n; i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); pair < llong, llong > opt1 = {dp[i - 1][0].first + a[i] - x, dp[i - 1][0].second + 1}; pair < llong, llong > opt2 = {dp[i - 1][1].first + a[i], dp[i - 1][1].second}; dp[i][1] = max(opt1, opt2); } return max(dp[n][0], dp[n][1]); } void solve() { llong ans = 0; llong left = -1; llong right = 1e18; llong mid; while(right - left > 1) { mid = left + (right - left) / 2; if(check(mid).second >= k) left = mid; else right = mid; } cout << check(left).first + (llong)left * k << endl; } int main() { read(); solve(); return 0; }