#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<int> a(n + 1); int cur = 0; long long ans1 = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; if(a[i] < 0){ cur += 1; } ans1 += a[i]; } if(cur == 0) { cout << ans1 << endl; } else if(k == 1){ long long C = max(0, a[1]); long long sum = max(0, 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{ vector<vector<long long>> mx(n + 1, vector<long long>(n + 1)); for (int i = 1; i <= n; i++) { long long sum = 0, x = 0; for (int j = i; j <= n; j++) { sum += a[j]; x = max(x, sum); if (sum < 0) { sum = 0; } mx[i][j] = x; } } vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { for (int r = 0; r < i; r++) { dp[i][j] = max(dp[i][j], dp[r][j - 1] + mx[r + 1][i]); } } } cout << dp[n][k] << endl; return 0; } }