#include <bits/stdc++.h> using namespace std; using ll = long long; struct Seg { ll sum; int l, r; }; // Tìm đoạn con có tổng lớn nhất (Kadane) và trả về sum + vị trí Seg best_segment(const vector<ll>& a) { ll best = LLONG_MIN, cur = 0; int start = 1, bestL = 1, bestR = 1; for (int i = 1; i < (int)a.size(); i++) { if (cur + a[i] < a[i]) { cur = a[i]; start = i; } else { cur += a[i]; } if (cur > best) { best = cur; bestL = start; bestR = i; } } return {best, bestL, bestR}; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin >> N >> K; vector<ll> a(N + 1); for (int i = 1; i <= N; i++) cin >> a[i]; ll total_ans = 0; for (int k = 0; k < K; k++) { Seg seg = best_segment(a); if (seg.sum < 0) break; // không lấy đoạn âm total_ans += seg.sum; // XÓA đoạn này for (int i = seg.l; i <= seg.r; i++) { a[i] = 0; // hoặc a[i] = -1e18; } } cout << total_ans << "\n"; return 0; }