//*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
//*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int ,int > pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn = 3e5+100;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);
#define int ll
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
int n , k;
ll dp[maxn];
ll sum[maxn];
int a[maxn];
struct segment{
int seg[maxn*4];
int lazy[maxn*4];
void build(int v = 1 , int l = 1 , int r = n + 1){
if(r - l == 1){
seg[v] = dp[l] - sum[l];
return;
}
int mid = (l + r) / 2;
build(2*v , l , mid);
build(2*v + 1 , mid , r);
seg[v] = max(seg[2*v] , seg[2*v + 1]);
}
void shift(int v , int l , int r){
seg[v] += lazy[v];
if(r - l > 1)
lazy[2*v] += lazy[v] , lazy[2*v + 1] += lazy[v];
lazy[v] = 0;
}
void update(int L , int R , int x, int v = 1 , int l = 1 , int r = n + 1){
shift(v , l , r);
if(r <= L or R <= l)
return;
if(L <= l and r <= R){
lazy[v] += x;
shift(v , l , r);
return;
}
int mid = (l + r) / 2;
update(L , R , x , 2*v , l , mid);
update(L , R , x , 2*v + 1 , mid , r);
seg[v] = max(seg[2*v] , seg[2*v + 1]);
}
int query(int L , int R , int v = 1 , int l = 1 , int r = n + 1){
shift(v , l , r);
if(r <= L or R <= l)
return(0);
if(L <= l and r <= R)
return(seg[v]);
int mid = (l + r)/2;
return(max(query(L , R , 2*v , l , mid) , query(L , R , 2*v + 1, mid , r)));
}
};
segment seg; //shans 100
void sub1(){ //10 + 11 (+ 20 ?)
ll mn = 0;
for(int i = 1 ; i <= n ; i ++)
dp[i] = max({dp[i] , dp[i - 1] , sum[i] - mn}) , mn = min(mn , sum[i]);
for(int j = 2 ; j <= k ; j ++){
seg.build();
for(int i = 1 ; i <= n ; i ++ )
dp[i] = max(dp[i-1] , sum[i] + seg.query(1 , i));
}
dokme(dp[n]);
}
void sub2(){ //18
ll ans = 0;
ll mn = 0;
for(int i = 1 ; i <= n ; i ++)
ans = max(ans , sum[i] - mn) , mn = min(mn , sum[i]);
dokme(ans);
}
void sub3(){ //8
ll ans = 0;
for(int i = 1 ; i <= n ; i ++)
ans += max(0LL , a[i]);
dokme(ans);
}
void sub4(){ //4
dokme(sum[n]);
}
int32_t main(){
migmig;
cin >> n >> k;
int cnt = 0;
for(int i = 1 ; i <= n ; i ++)
cin >> a[i] , cnt+=(a[i] < 0);
for(int i = 1; i <= n ; i ++)
sum[i] = sum[i-1] + a[i];
if(n <= 2000 and k <= 2000){
sub1();
}
if(*min_element(a+1 , a + n + 1) >= 0)
sub4();
if(k == 1){
sub2();
}
if(cnt <= 1){
sub3();
}
dokme("8===o");
return(0);
}
