#include <iostream>
#include <cstdio>
#define MAXN 10050
#define MAXK 1050
#define inf 0x3f3f3f3f

using namespace std;

int n, k, a[MAXN], pre[MAXN];
int din[MAXK][MAXN];

void dinam()
{
	for (int i = 1, j; i <= k; i++) {
		int crtmax = din[i-1][0];
		for (j = 1 + (i==1); j <= n; j++) {
            din[i][j] = max(din[i][j-1], crtmax) + a[j];
            crtmax = max(crtmax, din[i-1][j]);
		}
    }
}

int solve()
{
	for (int i = 1; i <= k; i++)
		din[i][0] = -inf;
	din[1][1] = a[1];
    dinam();
    int att1 = 0;
    for (int i = 1; i <= n; i++)
		att1 = max(att1, din[k][i]);
	for (int i = 0; i <= n; i++)
		din[0][i] = -inf;

	dinam();
    for (int i = 1; i <= n; i++)
		din[k][i] = max(din[k][i-1], din[k][i]);
    for (int i = 1; i <= n; i++)
		att1 = max(att1, din[k][i] + pre[n]-pre[i]);
	return att1;
}

int main()
{
    freopen("ferma.in", "r", stdin);
    freopen("ferma.out", "w", stdout);

    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		pre[i] = pre[i-1] + a[i];
    }
    int rez = solve();
    printf("%d", rez);

    return 0;
}