n, k = gets.split.map &:to_i

#少タイプmany寿司のとき・・・　

org_sushi = []

n.times{
	org_sushi << (gets.split.map &:to_i)
}

org_sushi = org_sushi.sort{|a,b| b[1] <=> a[1]}
type_count = org_sushi.map{|x| x[0]}.uniq.size

total = 0

cand = []

[k, type_count].min.downto(1){ |i|
	total = 0
	sushi = org_sushi.clone
	#i種類使う場合のMAX
	types = {}
	k.times {
		if types.size >= i then
			total += sushi[0][1]
			sushi.shift
		else
			#まだ採用していないネタ
			idx = sushi.index{|x| types[x[0]] == nil }
			types[sushi[idx][0]] = true
			total += sushi[idx][1]
			sushi.delete_at(idx)
		end
	}
	cand << total + i * i
}

puts cand.max
