#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define el '\n'
#define fu(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fd(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)
#define fa(x, a) for(auto x : a)
#define re(i, n) fu(i,0,n - 1)
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
#define pof pop_front
#define pob pop_back
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define MP make_pair
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define db double
#define ld long double
#define squr(a) 1LL * (a) * (a)
using namespace std;
const int maxn = 3e5;
const ll lim = 1e9;
const ll inf = 1e18;
const ll mod = 1e9 + 7; /// 1007050321
const ll base = 33137;
template<class T1,class T2>
bool maximize(T1 &a,T2 b){
if(a < b){
a = b;
return 1;
}
return 0;
}
template<class T1,class T2>
bool minimize(T1 &a,T2 b){
if(a > b){
a = b;
return 1;
}
return 0;
}
template<class T1,class T2>
void Add(T1 &a,T2 b){
a += b;
if(a >= mod) a -= mod;
if(a < 0) a += mod;
return;
}
template<class T1>
void temp_compress(vector<T1> &a){
sort(all(a));
a.resize(unique(all(a)) - a.begin());
return;
}
ll max(ll a,ll b){return (a > b ? a : b);}
ll min(ll a,ll b){return (a < b ? a : b);}
bool takeBit(ll th,ll n){return ((n >> th) & 1LL);}
ll gcd(ll a,ll b){return (__gcd(a, b));}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch(). count());
#define rand rd
ll ran(ll lo,ll hi){
return (lo + rand() % (hi - lo + 1));
}
//int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
//int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dx[3] = {1, 0, 0};
int dy[3] = {0, -1, 1};
int n,m;
ll a[maxn + 5];
bool check_sub1(){
fu(i,1,n) if(a[i] < 0) return 0;
return 1;
}
namespace sub1 {
void solve(){
ll sum = 0LL;
fu(i,1,n) sum += a[i];
cout<<sum;
return;
}
}
bool check_sub2(){
int cnt = 0;
fu(i,1,n) if(a[i] < 0) ++cnt;
return (cnt == 1);
}
namespace sub2 {
void solve(){
int pos = 0;
fu(i,1,n) if(a[i] < 0){
pos = i;
break;
}
ll sum1 = 0LL, sum2 = 0LL;
fu(i,1,pos - 1) sum1 += a[i];
fu(i,pos + 1,n) sum2 += a[i];
if(m > 1) cout<<sum1 + sum2;
else{
ll sum = sum1 + sum2 + a[pos];
cout<<max({sum, sum1, sum2});
}
return;
}
}
bool check_sub3(){
return (m == 1);
}
namespace sub3 {
void solve(){
ll res = 0LL, sum = 0LL;
fu(i,1,n){
sum += a[i];
maximize(res, sum);
maximize(sum, 0LL);
}
cout<<res;
return;
}
}
bool check_sub5(){
return (n <= 300);
}
namespace sub5 {
ll dp[305][305], pre[305];
void solve(){
fu(i,1,n) pre[i] = pre[i - 1] + a[i];
memset(dp, -0x3f, sizeof dp);
fu(i,0,n) dp[i][0] = 0LL;
re(i, n) fu(j,0,min(i, m)){
if(j < m) maximize(dp[i][j + 1], dp[i][j]);
maximize(dp[i + 1][j], dp[i][j]);
if(j < m) fu(k,i + 1,n) maximize(dp[k][j + 1], dp[i][j] + pre[k] - pre[i]);
}
// fu(i,1,n){
// cout<<"Position : "<<i<<el;
// fu(j,1,min(i, m)) cout<<dp[i][j]<<' ';
// cout<<el;
// }
cout<<dp[n][m];
return;
}
}
bool check_sub6(){
return (n <= 2000);
}
namespace sub6 {
ll dp[2005][2005], g[2005][2005];
void solve(){
fu(i,1,n) fu(j,1,m){
dp[i][j] = dp[i - 1][j] + a[i];
if(j > 1) maximize(dp[i][j], g[i - 1][j - 1] + a[i]);
g[i][j] = max(g[i - 1][j], dp[i][j]);
}
ll res = 0LL;
fu(j,1,m) maximize(res, dp[n][j]);
cout<<res;
return;
}
}
void input(){
cin>>n>>m;
fu(i,1,n) cin>>a[i];
return;
}
int main(){
fast
// freopen("feas.INP", "r", stdin);
// freopen("feas.OUT", "w", stdout);
// clock_t start = clock();
input();
if(check_sub1()) return sub1::solve(), 0;
if(check_sub2()) return sub2::solve(), 0;
if(check_sub3()) return sub3::solve(), 0;
if(check_sub5()) return sub5::solve(), 0;
if(check_sub6()) return sub6::solve(), 0;
// cerr<<el<<"Time elapsed : "<<(clock() - start)<<el;
return 0;
}
