#include <iostream> #include <cstring> using namespace std; void speed() { ios_base::sync_with_stdio(false); cin.tie(); cout.tie(); } const int MAXN = (int)3e5 + 5; long long dp[MAXN][2]; long long cnt[MAXN][2]; int a[MAXN], n, k; void read() { cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; } int check(long long cost) { memset(dp, 0, sizeof(dp)); memset(cnt, 0, sizeof(cnt)); dp[1][0] = 0; cnt[1][0] = 0; dp[1][1] = a[1] - cost; cnt[1][1] = 1; for(int i = 2; i <= n; i++) { //cout << i << endl; 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] + a[i] - cost > dp[i - 1][1] + a[i]) { dp[i][1] = dp[i - 1][0] + a[i] - cost; cnt[i][1] = cnt[i - 1][0] + 1; } else { dp[i][1] = dp[i - 1][1] + a[i]; cnt[i][1] = cnt[i - 1][1]; } } if(max(dp[n][0] + (k * cost), dp[n][1] + (k * cost)) == dp[n][0] + (k * cost)) return cnt[n][0]; else return cnt[n][1]; } void binSearch() { long long L = 0, R = 1e18, mid; while(L <= R) { mid = (L + R) / 2; long long ch = check(mid); if(ch > k) L = mid + 1; else R = mid - 1; } if(R == -1) R = 0; //cout << L << ' ' << mid << ' ' << R << endl; cout << max(dp[n][0] + (cnt[n][0] * L), dp[n][1] + (cnt[n][1] * L)) << endl; } int main() { speed(); read(); binSearch(); return 0; }