unittest
{
	assert( [ "3 7", "1 6 3" ].parse.expand.solve == 14 );
	assert( [ "4 9", "7 4 0 3" ].parse.expand.solve == 46 );
	assert( [ "1 0", "1000000000000" ].parse.expand.solve == 1000000000000 );
	
	assert( [ "3 4", "1 1 4" ].parse.expand.solve == 12 );		// 追加ケース
	assert( [ "3 4", "1 2 4" ].parse.expand.solve == 11 );		// 追加ケース
}
 
 
 
import std.algorithm;
import std.conv;
import std.format;
import std.functional;
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 as = input.front.split.to!( long[] );
	return tuple( nk[ 1 ], as );
}
 
auto solve( long k, long[] as )
{
	// Kの2進数表記を取得（桁数を使う）
	auto kb = format( "%b", k );

	// 各桁ごとに、Asを足し算
	auto cs = new long[ kb.length ];
	foreach( a; as )
	{
		auto r = a % 2L ^^ kb.length;		// Kの桁数以上は考えなくていいので捨てる
		for( auto i = 0L; 0 < r; i++ )
		{
			cs[ i ] += r % 2;
			r /= 2;
		}
	}
	
	// 各桁ごとに、Xの同じ桁を1にしたときのf(X)の増分を計算
	auto vs = new long[ kb.length ];
	foreach( long i, c; cs )
	{
		auto v = 2L ^^ i * ( ( cast( long ) cs.length ) - c * 2 );
		if( 0 < v ) vs[ i ] = v;		// 増分がマイナスになるものは除いておくと後が楽
	}
	
	// f(X)の最大値を計算
	return as.sum + solve2( k, vs );
}

long solve2( long k, long[] vs, bool greedy = false )
{
	if( vs.length == 0 ) return 0L;
	
	// XがKを超える可能性が残っていない場合は、単純に増分の合計を返す
	if( greedy ) return vs.sum;

	// XがKを超える可能性が残っている場合は、超えないように全検索する
	auto d = 2L ^^ ( vs.length - 1 );
	if( ( k & d ) == 0 )
	{
		return memoize!solve2( k % d, vs[ 0 .. $ - 1 ], false );
	}
	else
	{
		return max(
			memoize!solve2( k % d, vs[ 0 .. $ - 1 ], true ),		// Kの最上位ビットが1のときにXの最上位ビットを0にしたので、もうXがKを超える可能性は無くなる
			memoize!solve2( k % d, vs[ 0 .. $ - 1 ], false ) + vs[ $ - 1 ]
		);
	}
}
