#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n, m, ans, f[10005], a[10005], b[10005];

int main()
{
	freopen("KPengshuangcang.in", "r", stdin);
	freopen("KPengshuangcang.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) 
	{
		scanf("%d", a+i);
		b[i] = a[i] + b[i-1];
	}
	
	for(int i = 1; i <= n; i++)
	{
		int mn = b[i-1];
		for(int j = i-1; j >= 0; j--) mn = min(mn, b[j]);
		f[i] = b[i] - mn;
	}
	
	for(int i = 2; i <= m; i++)
	for(int j = n; j >= 1; j--)
	{
		int mx = a[j], sum = a[j];
		f[j] = a[j] + f[j-2]; 
		for(int k = j-1; k >= 2; k--)
		{
			mx = max(mx, sum+=a[k]);
			f[j] = max(f[j], f[k-2]+mx);
		}
	}
	
	for(int i = m*2; i <= n; i++) ans = max(ans, f[i]);
	printf("%d", ans);
	return 0;
}