#include <fstream>

using namespace std;

#define MAX_N 10005
#define MAX_K 1005

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

int N, K, Sol;
int V[MAX_N], A[MAX_N][MAX_K], B[MAX_N][MAX_K];

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

void non_circ()
{
	for(int i = 0; i <= N; ++i)
		for(int j = 0; j <= K; ++j)
			if(j > i)
				B[i][j] = A[i][j] = -0x3f3f3f3f;
	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= K; ++j)
			A[i][j] = max(A[i-1][j-1], max(A[i-1][j], B[i-1][j-1])) + V[i],
			B[i][j] = max(A[i-1][j], B[i-1][j]);

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

void circ()
{
	memset(A, 0, sizeof A);
	for(int i = 0; i <= N; ++i)
		for(int j = 0; j <= K; ++j)
			if(j > i)
				B[i][j] = A[i][j] = -0x3f3f3f3f;
	A[1][1] = V[1];
	B[1][1] = V[1];
	++K;
	for(int i = 2; i <= N; ++i)
		for(int j = 1; j <= K; ++j)
		{
			if(j > 1) 
				A[i][j] = max(A[i-1][j-1], max(A[i-1][j], B[i-1][j-1])) + V[i];
			else
				A[i][j] = A[i-1][j] + V[i];
			B[i][j] = max(A[i-1][j], B[i-1][j]);
		}
			
	printf("%d\n", A[2][1]);	
	Sol = max(Sol, A[N][K]);
	fout << Sol;
}

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