//In The Name of Allah
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair < int , int > pii;
typedef pair < ll , ll > pll;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())
const int N = 3e5 + 10;
const int M = 2010;
const ll mod = 1e9 + 7;
const int inf = 1e9 + 10;
ll a[N], dp[2][M][M];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n, k, mn = inf, cn = 0, sum = 0;
cin >> n >> k;
for (int i = 1; i <= n; i ++){
cin >> a[i];
mn = min(mn, a[i]);
cn += a[i] < 0;
sum += a[i];
}
if (0 <= mn)
return cout << sum, 0;
if (cn == 1){
ll pre = 0, suf = 0;
for (int i = 1; i <= n && 0 <= a[i]; i ++)
pre += a[i];
for (int i = n; i >= 1 && 0 <= a[i]; i --)
suf += a[i];
if (2 <= k)
return cout << sum - mn, 0;
return cout << max({sum, pre, suf}), 0;
}
if (k == 1){
ll ans = 0, cur = 0;
for (int i = 1; i <= n; i ++){
cur = max(0LL, cur + a[i]);
ans = max(ans, cur);
}
return cout << ans, 0;
}
if (n <= 2000 && k <= 2000){
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= k; j ++){
dp[0][i][j] = a[i] + max(dp[0][i - 1][j], dp[1][i - 1][j - 1]);
dp[1][i][j] = max(dp[1][i - 1][j], dp[0][i][j]);
}
}
return cout << dp[1][n][k], 0;
}
return 0;
}
