#include <bits/stdc++.h> using namespace std; #define int long long constexpr int N = 2005; int dp[N][N][2], a[N]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; } int cnt = 0; for (int i = 1; i <= n; i++) { if (a[i] < 0) { cnt++; } } if (k == 1 || cnt == 0) { int ans = 0, sum = 0; for (int i = 1; i <= n; i++) { sum += a[i]; if (sum < 0) { sum = 0; } ans = max(ans, sum); } cout << ans << '\n'; } else if (cnt == 1) { int left = 0, right = 0; for (int i = 1; i <= n; i++) { if (a[i] < 0) break; left += a[i]; } for (int i = n; i >= 1; i--) { if (a[i] < 0) break; right += a[i]; } cout << left + right << '\n'; } else { for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]); dp[i][j][1] = max(dp[i - 1][j][1] + a[i], dp[i - 1][j - 1][0] + a[i]); } } cout << max(dp[n][k][0], dp[n][k][1]) << '\n'; } return 0; }