#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); for (int i = 1; i <= n; i++) { cin >> a[i]; } 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; }