#include <bits/stdc++.h> #define endl "\n" using namespace std; const int MAXN = 3e5+5; long long n,k; long long a[MAXN]; void read() { cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; } long long dp[MAXN][2]; long long cnt[MAXN][2]; long long check(long long c, bool add) { for(int i = 0; i <= n; i++) dp[i][0] = dp[i][1] = cnt[i][0] = cnt[i][1] = 0; dp[0][1] = -c; cnt[0][1] = 1; for(int i = 1; i <= n; i++) { 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] == dp[i-1][1]) cnt[i][0] = max(cnt[i-1][1],cnt[i-1][0]); } if(dp[i-1][0] - c > dp[i-1][1]) { dp[i][1] = dp[i-1][0] - c + a[i]; 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(dp[i-1][0] - c == dp[i-1][1]) cnt[i][1] = max(cnt[i-1][0] + 1, cnt[i-1][1]); } } int b = 1; if(dp[n][0] > dp[n][1]/* || (dp[n][0] == dp[n][1] && cnt[n][0] > cnt[n][1])*/) b = 0; if(add) return dp[n][b] + c*k; return (bool)cnt[n][b] >= k; } void solve() { long long l = 1, r = 1e15; long long mid; while(l <= r) { mid = (l+r)/2; if(check(mid,0)) l = mid+1;///absolutno taka e else r = mid-1; } //cout << r << endl; cout << check(r,1) << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); read(); solve(); return 0; }