#include <bits/stdc++.h>
using namespace std;
#define fox(i, n) for(int i = 0; i < (n); ++i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define rin(i, a, b) for(int i = (a); i <= (b); ++i)
#define rev(i, a, b) for(int i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()
#define int long long
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define F first
#define S second
#define pb push_back
#define eb emplace_back
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); }
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); }
int MSB(int x) { return bit_width((unsigned long long)x)-1; }
int LSB(int x) { return countr_zero((unsigned long long)x); }
ii BS(int L, int H, function<int(int)>P) {
while(abs(L-H)>1){
int M=midpoint(L,H);
if(P(M))H=M;
else L=M;
}
return{L,H};
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int urand(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }
const int inf = 1e17;
//const int N = 2*3e5+1;
const int N = 2*301;
int a[N],psa[N],dp[N][2],cnt[N][2],Dp[N][N];
// Dp[i][j] = best sum if we split 1..i into j subarrays
void solve(){
int n,k;cin>>n>>k;
rin(i,1,n)cin>>a[i];
rin(i,n+1,2*n)a[i]=0;
n*=2;
auto opt = [&](int l) -> ii {
dp[1][0]=0;
cnt[1][0]=0;
if(ckmax(dp[1][0],a[1]+l))cnt[1][0]=1;
dp[1][1]=a[1];
cnt[1][1]=0;
rin(i,2,n){
// CALC: dp[i][0]
// case 1: don't include a[i]
dp[i][0] = dp[i-1][0];
cnt[i][0] = cnt[i-1][0];
// case 2: include a[i] but something before too
if(ckmax(dp[i][0], dp[i-1][1] + a[i] + l))
cnt[i][0] = 1 + cnt[i-1][1];
// case 3: include a[i] but nothing before
if(ckmax(dp[i][0], dp[i-1][0] + a[i] + l))
cnt[i][0] = 1 + cnt[i-1][0];
// CALC: dp[i][1]
dp[i][1] = a[i] + max(dp[i-1][0], dp[i-1][1]);
if(dp[i-1][0] == dp[i-1][1])
cnt[i][1] = min(cnt[i-1][0], cnt[i-1][1]);
else if(dp[i-1][0] > dp[i-1][1])
cnt[i][1] = cnt[i-1][0];
else cnt[i][1] = cnt[i-1][1];
}
return {cnt[n][0],dp[n][0]};
};
auto Opt = [&]() -> int {
rin(i,1,n)psa[i]=psa[i-1]+a[i];
rin(i,1,n)rin(j,1,n){
Dp[i][j] = Dp[i-1][j];
rin(I,1,i)ckmax(Dp[i][j], psa[i] - psa[I-1] + Dp[I-1][j-1]);
}
return Dp[n][k];
};
int lo = -1e10; // cnt < k
int hi = 1e10; // cnt >= k
while((hi-lo)>1){
int mid=midpoint(lo,hi);
auto[cnt,val]=opt(mid);
if(cnt < k)lo=mid;
else hi=mid;
}
auto[cnt,val]=opt(hi);
val -= cnt*hi; // counteract the thing
//cout<<cnt<<' '<<val<<'\n';
//cout<<val<<'\n';
cout<<Opt()<<'\n';
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
//cout<<solve()<<'\n';
solve();
}
