#include<iostream>
using namespace std;
const int N = 5e5+5;
#define int long long
int n, k;
int a[N];
int f[N], Max[N], L[N];

inline bool check(int d){
	for(int i = 1; i <= n; i++)
		f[i] = Max[i] = L[i] = 0;
	if( a[1] + d >= 0 ){
		Max[1] = f[1] = a[1] + d;
		if( a[1] + d == 0 )
			L[1] = 0;
		else
			L[1] = 1;
	}
	for(int i = 2; i <= n; i++){
		if( a[i] + d >= 0 ){
			f[i] += Max[i - 2] + a[i] + d;
			if( f[i] > Max[i - 1] ){
				Max[i] = f[i];
				if( a[i] + d > 0 )
					L[i] = L[i - 2] + 1;
				else
					L[i] = L[i - 2];
			}
			else if( f[i] == Max[i - 1] ){
				Max[i] = Max[i - 1];
				if( a[i] + d > 0 )
					L[i] = min(L[i - 1], L[i - 2] + 1);
				else
					L[i] = min(L[i - 1], L[i - 2]);
			}
			else{
				Max[i] = Max[i - 1];
				L[i] = L[i - 1];
			}
		}
		else{
			Max[i] = Max[i - 1];
			L[i] = L[i - 1];
		}
	}
	if( L[n] <= k )
		return 1;
	return 0;
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    	cin >> a[i];
    
    if( check(0) ){
    	cout << Max[n];
    	return 0;
    }
    int l = -1e7, r = 0, ans = 0;
    while( l != r ){
    	int mid = (l + r) >> 1;
    	if( check(mid) ){
    		l = mid + 1;
    		ans = max(ans, Max[n] - L[n] * mid);
    	}
    	else
    		r = mid;
    }
    cout << ans;
	return 0;
}