unittest
{
	assert( [ "6 4", "-10 8 2 1 2 6" ].parse.expand.solve == 14 );
	assert( [ "6 4", "-6 -100 50 -2 -5 -3" ].parse.expand.solve == 44 );
	assert( [ "6 3", "-6 -100 50 -2 -5 -3" ].parse.expand.solve == 0 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nk = input.front.split.to!( long[] );
	input.popFront;
	auto vs = input.front.split.to!( long[] );
	return tuple( nk[ 1 ], vs );
}

auto solve( long k, long[] vs )
{
	return solve2( k, vs, [], 0L );
}

long solve2( long k, long[] vs, long[] vms, long vt )
{
	if( k == 0 ) return vt;
	
	auto vtm = vt;
	
	// 操作AorB
	if( 0 < vs.length )
	{
		vtm = max( vtm, solve2( k - 1, vs[ 1 .. $     ], ( 0 <= vs.front ) ? vms : vms.dup ~ vs.front, vt + vs.front ) );
		vtm = max( vtm, solve2( k - 1, vs[ 0 .. $ - 1 ], ( 0 <= vs.back  ) ? vms : vms.dup ~ vs.back,  vt + vs.back  ) );
	}
	
	// 操作CorD（どうせABのあとにやるので区別不要）
	if( 0 < vms.length )
	{
		vms.sort!();
		vtm = max( vtm, vt - vms[ 0 .. min( k, $ ) ].sum );
	}
	
	return vtm;
}
