import std.stdio;
import std.algorithm;
import std.array;
import std.conv;
import std.datetime;
import std.numeric;
import std.math;
import std.string;

string my_readln() { return chomp(readln()); }

void main()
{
	auto tokens = my_readln().split();
	auto N = tokens[0].to!ulong;
	auto K = tokens[1].to!ulong;
	ulong[] t, d;
	foreach (i; 0..N)
	{
		auto tokens2 = my_readln().split();
		t ~= tokens2[0].to!ulong - 1;
		d ~= tokens2[1].to!ulong;
	}
	
	auto index = new long[](N);
	makeIndex!"a > b"(d, index);
	auto used = new ulong[](N);
	auto types = new ulong[](N);
	ulong[] pt, tc;
	pt.length = 1;
	tc.length = 1;
	foreach (i; 0..K)
	{
		auto j = index[i];
		used[j] = 1;
		++types[t[j]];
		pt[0] += d[j];
	}
	foreach (e; types)
	{
		if (e != 0) ++tc[0];
	}

	foreach_reverse (i, e; index)
	{
		auto j = e;
		if (used[j] == 0) continue;
		if (types[t[j]] < 2) continue;
		used[j] = 0;
		--types[t[j]];
		ulong newPt = pt[$-1] - d[j];
		//stderr.writeln(j, " ", d[j]);
		foreach (i2; index)
		{
			auto j2 = index[i2];
			if (used[j2] == 1) continue;
			if (types[t[j2]] != 0) continue;
			used[j2] = 1;
			++types[t[j2]];
			newPt += d[j2];
			pt ~= newPt;
			//stderr.writeln(types);
			break;
		}
	}

	ulong ans = pt[0] + pow(tc[0], 2);
	foreach (i, e; pt[1..$])
	{
		//stderr.writeln(e, " ", pow(tc[0] + i + 1, 2));
		ans = max(ans, e + pow(tc[0] + i + 1, 2));
	}

	writeln(ans);
	stdout.flush();
}