local n = io.read("n")
local k = io.read("n")
local list = {}
for _ = 1, n do
	local t = io.read("n")
	local d = io.read("n")
	table.insert(list, {t, d})
end
table.sort(list, function(a, b)
	return a[2] > b[2]
end)

local type2num = {}
local xcnt = 0
local total = 0
for i = 1, k do
	local node = list[i]
	local t = node[1]
	local d = node[2]
	local num = type2num[t]
	if not num then
		xcnt = xcnt + 1
		num = 0
	end
	num = num + 1
	type2num[t] = num
	total = total + d
end

local g = total + xcnt * xcnt
local maxv = g
local sp1 = k
local sp2 = k + 1
for i = xcnt + 1, n do
	local v1, v2
	while (sp1 > 0) do
		local node = list[sp1]
		sp1 = sp1 - 1
		local t = node[1]
		if type2num[t] > 1 then
			v1 = node[2]
			type2num[t] = type2num[t] - 1
			break
		end
	end
	while (sp2 <= n) do
		local node = list[sp2]
		sp2 = sp2 + 1
		local t = node[1]
		if not type2num[t] then
			v2 = node[2]
			type2num[t] = 1
			break
		end
	end
	if v1 and v2 then
		total = total - v1 + v2
		g = total + i * i
		if g > maxv then
			maxv = g
		end
	else
		break
	end
end

print(maxv)