#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
const int MAXN = 3610, INF = ~0U >> 2;
int n, m, A[MAXN], F[2][MAXN][3], res = 0;
void init()
{
	scanf("%d%d", &n, &m);
	re(i, n) scanf("%d", &A[i]);
}
void solve()
{
	if (!n) return; else if (n == m) {
		res = 0; re(i, n) res += A[i];
		int minv = INF; re(i, n) if (A[i] < minv) minv = A[i]; res -= minv; return;
	}
	re3(i, 0, m) re(j, 3) re(k, 2) F[k][i][j] = -INF; F[0][0][0] = F[0][1][1] = 0; bool FF = 0; int _j;
	re2(i, 1, n) {
		F[!FF][0][0] = 0; F[!FF][0][1] = F[!FF][0][2] = -INF;
		if (i + 1 <= m) _j = i + 1; else _j = m;
		re1(j, _j) {
			F[!FF][j][0] = F[FF][j][0] >= F[FF][j][2] ? F[FF][j][0] : F[FF][j][2];
			F[!FF][j][1] = F[FF][j - 1][0];
			F[!FF][j][2] = (F[FF][j - 1][1] >= F[FF][j - 1][2] ? F[FF][j - 1][1] : F[FF][j - 1][2]) + A[i];
		}
		FF = !FF;
	}
	re(i, 3) if (F[FF][m][i] > res) res = F[FF][m][i];
	if (n == 1) return;
	re3(i, 0, m) re(j, 3) re(k, 2) F[k][i][j] = -INF; F[0][1][2] = A[0]; FF = 0;
	re2(i, 1, n) {
		F[!FF][0][0] = 0; F[!FF][0][1] = F[!FF][0][2] = -INF;
		if (i + 1 <= m) _j = i + 1; else _j = m;
		re1(j, _j) {
			F[!FF][j][0] = F[FF][j][0] >= F[FF][j][2] ? F[FF][j][0] : F[FF][j][2];
			F[!FF][j][1] = F[FF][j - 1][0];
			F[!FF][j][2] = (F[FF][j - 1][1] >= F[FF][j - 1][2] ? F[FF][j - 1][1] : F[FF][j - 1][2]) + A[i];
		}
		FF = !FF;
	}
	re2(i, 1, 3) if (F[FF][m][i] > res) res = F[FF][m][i];
}
void pri()
{
	printf("%d\n", res);
}
int main()
{
    init();
    solve();
    pri();
    return 0;
}