#include <fstream>

using namespace std;

#define MAX_N 10005
#define MAX_K 1005

#define INF 0x3f3f3f3f

ifstream fin ("ferma.in");
ofstream fout ("ferma.out");

int N, K, Sol;
int V[MAX_N];

void citire()
{
	fin >> N >> K;
	
	for(int i = 1; i <= N; ++i)
		fin >> V[i];
}

void non_circ()
{
	int A[2][MAX_K], B[2][MAX_K], crt, ant;
	for(int i = 1; i <= K; ++i)
		A[0][i] = B[0][i] = -INF; 
	for(int i = 1; i <= N; ++i)
	{
		crt = i & 1;
		ant = crt ^ 1;
		
		memset(A[crt], 0, sizeof A[crt]);
		memset(B[crt], 0, sizeof B[crt]);
		
		for(int j = i+1; j <= K; ++j)
			B[crt][j] = A[crt][j] = -INF;
		for(int j = 1; j <= min(i, K); ++j)
			A[crt][j] = max(A[ant][j-1], max(A[ant][j], B[ant][j-1])) + V[i],
			B[crt][j] = max(A[ant][j], B[ant][j]);
	}

	Sol = max(A[crt][K], B[crt][K]);
}

void circ()
{
	int A[2][MAX_K], B[2][MAX_K], crt, ant;
	for(int i = 2; i <= K; ++i)
		A[1][i] = B[1][i] = -INF; 
	A[1][1] = V[1];
	B[1][1] = V[1];
	++K;
	for(int i = 2; i <= N; ++i)
	{
		crt = i & 1;
		ant = crt ^ 1;
		
		memset(A[crt], 0, sizeof A[crt]);
		memset(B[crt], 0, sizeof B[crt]);
		
		for(int j = i+1; j <= K; ++j)
			B[crt][j] = A[crt][j] = -INF;
		for(int j = 1; j <= min(i, K); ++j)
		{
			if(j > 1) 
				A[crt][j] = max(A[ant][j-1], max(A[ant][j], B[ant][j-1])) + V[i];
			else
				A[crt][j] = A[ant][j] + V[i];
			B[crt][j] = max(A[ant][j], B[ant][j]);
		}
	}
				
	Sol = max(Sol, A[crt][K]);
	fout << Sol;
}

int main()
{
	citire();
	non_circ();
	circ();
}