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 );
	
	assert( [ "6 8", "-10 8 2 1 2 -6" ].parse.expand.solve == 13 );		// 追加ケース
}


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 )
{
	// 左からk個までの累積和を計算、マイナス値を集計
	auto lts = new long[]( 1 + min( k, vs.length ) );
	for( auto i = 1L; i < lts.length; i++ ) lts[ i ] = lts[ i - 1 ] + vs[ i - 1 ];
	
	// 右からk個までの累積和を計算
	auto rts = new long[]( 1 + min( k, vs.length ) );
	for( auto i = 1L; i < rts.length; i++ ) rts[ i ] = rts[ i - 1 ] + vs[ $ - i ];
	
	// 左と右の累積和を組み合わせて最大値を取得
	auto ans = 0L;
	long[] lms;
	foreach( li, lt; lts )
	{
		// 左側のマイナスの宝石を収集
		if( 0 < li && vs[ li - 1 ] < 0 ) lms ~= vs[ li - 1 ];
		
		long[] rms;
		foreach( ri, rt; rts )
		{
			if( k < li + ri || vs.length < li + ri ) break;
			
			// 右側のマイナスの宝石を収集
			if( 0 < ri && vs[ $ - ri ] < 0 ) rms ~= vs[ $ - ri ];
			
			// 操作回数がまだ残っている場合はマイナスの宝石を捨てる
			auto dt = ( lms ~ rms ).sort().take( k - li - ri ).sum;
			
			ans = max( ans, lt + rt - dt );
		}
	}
	return ans;
}
