#include <bits/stdc++.h> using namespace std; #define pb push_back #define int long long const int MOD = 1e9 + 7; const int INF = 1e15; const int N = 1e6; int n, m, k, a, b, c, d, h, l, r, q, u, v, x, y; vector<int> arr(N); vector<int> all; void build() { for(int i = 0; i<n; i++) { l = i; h = 0; if(arr[i] < 0) { while(l<n && arr[l] < 0) { h += arr[l]; l++; } } else { while(l<n && arr[l] >= 0) { h += arr[l]; l++; } } all.pb(h); i = l-1; } } void combine() { while(x > k) { bool found = false; for(int i = 0; i<all.size(); i++) { if(all[i] >= 0) continue; if(abs(all[i]) <= (min(all[i+1], all[i-1]))) { all[i-1] += all[i+1]+all[i]; all.erase(all.begin()+i, all.begin()+i+2); found = true; x--; break; } } if(!found) break; } } void solve() { cin >> n >> k; for(int i = 0; i<n; i++) { cin >> arr[i]; } build(); x = 0; h = 0; for(auto j : all) { // cout << j << " "; if(j >= 0) { h += j; x++; } } // cout << "\n"; if(x <= k) { cout << h; return; } if(all[0] < 0) all.erase(all.begin()); if(all.back() < 0) all.pop_back(); // for(auto j : all) cout << j << " "; // cout << "\n"; combine(); // for(auto j : all) cout << j << " "; // cout << "\n"; vector<int> pos; c = 0; for(auto j : all) { if(j >= 0) { pos.pb(j); } } sort(pos.rbegin(), pos.rend()); c = 0; for(int i = 0; i<k; i++) { c += pos[i]; } cout << c; } int32_t main() { ios::sync_with_stdio(false); cout.tie(0); cin.tie(0); int tc = 1; // cin >> tc; while(tc--) { solve(); cout << "\n"; } return 0; }