unittest
{
	assert( [ "5 3", "1 9", "1 7", "2 6", "2 5", "3 1" ].solve == 26 );
	assert( [ "7 4", "1 1", "2 1", "3 1", "4 6", "4 5", "4 5", "4 5" ].solve == 25 );
	assert( [ "6 5", "5 1000000000", "2 990000000", "3 980000000", "6 970000000", "6 960000000", "4 950000000" ].solve == 4900000016 );
}



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

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

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = 0L;
	auto k = 0L;
	input.front.formattedRead!"%s %s"( n, k );
	auto tds = new long[ 2 ][ n ];
	foreach( ref td; tds )
	{
		input.popFront;
		td = input.front.split.to!( long[] );
	}
	tds.multiSort!( ( a, b ) => b[ 1 ] < a[ 1 ], ( a, b ) => a[ 0 ] < b[ 0 ] );
	
	// おいしい順にk個食べたときの満足ポイントを計算
	auto m = 0L;
	long[ long ] ts;
	foreach( td; tds[ 0 .. k ] )
	{
		ts[ td[ 0 ] ]++;
		m += td[ 1 ];
	}
	
	// ネタの種類が増えるように入れ替えたときの満足ポイントを計算
	auto ans = m + ts.keys.length.signed ^^ 2;
	auto p = k - 1;
	foreach( td; tds[ k .. $ ] )
	{
		if( td[ 0 ] in ts ) continue;
		
		while( 0 <= p && ts[ tds[ p ][ 0 ] ] <= 1 ) p--;
		if( p <= 0 ) break;
		
		ts[ tds[ p ][ 0 ] ]--;
		ts[ td[ 0 ] ]++;
		m -= tds[ p ][ 1 ] - td[ 1 ];
		p--;
		ans = max( ans, m + ts.keys.length.signed ^^ 2 );
	}
	return ans;
}
