#include <bits/stdc++.h> using namespace std; using ll = long long; struct Node { ll sum; // tổng đoạn con tốt nhất trong [L0..R0] int L0, R0; // biên của đoạn gốc int l, r; // đoạn con tốt nhất nằm trong [L0..R0] bool operator<(const Node& other) const { return sum < other.sum; // max-heap } }; // Kadane trong đoạn [L..R], trả về best subarray và biên gốc L..R Node get_best(const vector<ll>& a, int L, int R) { ll cur = 0, best = LLONG_MIN; int start = L, bestL = L, bestR = L; for (int i = L; i <= R; 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, L, R, 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]; priority_queue<Node> pq; // Bắt đầu từ toàn đoạn [1..N] Node root = get_best(a, 1, N); if (root.sum > 0) pq.push(root); ll ans = 0; while (K-- && !pq.empty()) { Node cur = pq.top(); pq.pop(); if (cur.sum <= 0) break; ans += cur.sum; // tách trái => [L0 .. l-1] if (cur.l > cur.L0) { Node left = get_best(a, cur.L0, cur.l - 1); if (left.sum > 0) pq.push(left); } // tách phải => [r+1 .. R0] if (cur.r < cur.R0) { Node right = get_best(a, cur.r + 1, cur.R0); if (right.sum > 0) pq.push(right); } } cout << ans << "\n"; return 0; }