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



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[] );
	auto tds = new long[][]( nk[ 0 ], 2 );
	foreach( ref td; tds )
	{
		input.popFront;
		td = input.front.split.to!( long[] );
	}
	return tuple( nk[ 1 ], tds );
}

auto solve( long k, long[][] tds )
{
	// 種類無視でおいしい順にソート
	tds.sort!( ( a, b ) => b[ 1 ] < a[ 1 ] );
	
	// 全種類数をカウント
	auto tm = tds.map!( ( td ) => td[ 0 ] ).array.sort().uniq.walkLength;
	
	// おいしい順にK個のところで分ける
	auto tds_g = tds.take( k );
	auto tds_l = tds.drop( k );
	
	// おいしい順だけでK個選んだ場合を計算
	auto ts = tds_g.map!( ( td ) => td[ 0 ] ).array.sort().group.assocArray;
	auto tc = ts.length;
	auto dt = tds_g.map!( ( td ) => td[ 1 ] ).sum;
	auto ans = tc * tc + dt;
	
	// 全種類網羅するまで、おいしい順の下から1つずつ選んでない種類に入れ替えて計算
	foreach_reverse( td_r; tds_g )
	{
		if( tm <= tc ) break;
		if( ts[ td_r[ 0 ] ] <= 1 ) continue;
		
		while( !tds_l.empty )
		{
			auto td_i = tds_l.front;
			tds_l.popFront;
			
			if( td_i[ 0 ] in ts ) continue;
			
			// 入れ替えた分を再計算
			ts[ td_r[ 0 ] ]--;
			ts[ td_i[ 0 ] ]++;
			tc++;
			dt -= td_r[ 1 ];
			dt += td_i[ 1 ];
			ans = max( ans, tc * tc + dt );		// 点数が大きいほうを取る
			break;
		}
	}
	
	return ans;
}
