#include <bits/stdc++.h> using namespace std; #define int long long constexpr int N = 2005; long long dp[N][N][2], a[N]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; int ans1 = 0; int cur = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; ans1 += a[i]; if(a[i] < 0){ cur += 1; } } if(cur == 0) { cout << ans1 << endl; } else if (cur == 1) { long long res = ans1; long long 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]; } if (k == 1) { cout << max({res, left, right}) << '\n'; } else { cout << max(res, left + right) << '\n'; } } else if(k == 1){ long long C = max(0LL, a[1]); long long sum = max(0LL, a[1]); for(int i = 2; i <= n; i++){ sum += a[i]; if(sum >= C){ C = sum; } else if(sum < 0){ sum = 0; } } cout << C; } 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; }