unittest
{
	assert( [ "5 3", "10 14 19 34 33" ].parse.expand.solve == 202 );
	assert( [ "9 14", "1 3 5 110 24 21 34 5 3" ].parse.expand.solve == 1837 );
	assert( [ "9 73", "67597 52981 5828 66249 75177 64141 40773 79105 16076" ].parse.expand.solve == 8128170 );
	
	assert( [ "5 3", "10 10 10 10 10" ].parse.expand.solve == 60 );		// 追加ケース
	assert( [ "100000 3", "100000".repeat( 100000 ).join( ' ' ) ].parse.expand.solve == 600000 );		// 追加ケース
}



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 nm = input.front.split.to!( long[] );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	return tuple( nm[ 1 ], as );
}

auto solve( long m, long[] as )
{
	as.sort!( ( x, y ) => y < x );
	
	// m通り以上の握手ができる最大のパワーを二分探索
	auto l = as[ $ - 1 ] * 2;
	auto r = as[ 0 ] * 2;
	while( l < r )
	{
		auto c = ( l + r + 1 ) / 2;
		
		// c以上のパワーの握手が何通りできるか計算
		auto n = 0L;
		auto j = as.length.signed;
		foreach( i, a; as )
		{
			for( ; 0 < j; j-- )
			{
				if( c <= a + as[ j - 1 ] )
				{
					n += j;
					break;
				}
			}
		}
		
		if( m <= n ) l = c;
		else         r = c - 1;
	}
	
	// 累積和表を作成
	auto ts = new long[ 1 + as.length ];
	foreach( i, a; as )
	{
		ts[ i + 1 ] = ts[ i ] + as[ i ];
	}
	
	// 最大幸福度を計算
	auto ans = 0L;
	auto n = 0L;
	auto z = long.max;
	auto j = as.length.signed;
	foreach( i, a; as )
	{
		for( ; 0 < j; j-- )
		{
			if( l <= a + as[ j - 1 ] )
			{
				ans += ( a * j ) + ts[ j ];
				n += j;
				z = min( z, a + as[ j - 1 ] );
				break;
			}
		}
	}
	ans -= z * ( n - m );		// 最小パワーのゲストが複数いるとm通りをオーバーしてしまうので削る
	return ans;
}
