require 'set'

N, K = gets.split.map &:to_i
Sushis = [*0...N].map{ gets.split.map &:to_i }


# Editorialを参考にした解法
# 1. まずSushisを美味しさ基礎点順に降順ソートし、先頭からK個選ぶ
Delicious_Sushis = Sushis.sort_by{|sushi| -sushi[1]}
selected_Sushis = Delicious_Sushis.take(K)
selected_Sushis_Point = selected_Sushis.inject(0){|sum, sushi| sum + sushi[1]}
num_selected_Sushis = selected_Sushis.size
selected_Groups_Set = selected_Sushis.map{|sushi| sushi[0]}.to_set
num_selected_Groups = selected_Groups_Set.size

# 2. selected_Sushisに含まれない種類のSushi Kindそれぞれについて、最大値の美味しさポイントを持つSushiを1つずつ取り出す
Unselected_Sushi_Groups = Delicious_Sushis.drop(K).group_by{|sushi| sushi[0]}
Unselected_but_Delicious_Sushis = Unselected_Sushi_Groups.values.map{|sushi_group| sushi_group.sort_by{|sushi| -sushi[1]}.first}

# 3. selected_Sushisについて、2のUnselected_but_Delicious_Sushisと交換可能なSushiについて求める
Changeable_Sushi = selected_Sushis.group_by{|sushi| sushi[0]}.values.select{|sushi_group| sushi_group.size >= 2}.map{|sushi_group| sushi_group.sort_by{|sushi| sushi[1]}.map{|sushi| sushi[1]}.take(sushi_group.size - 1)}.flatten.sort


# Unselected_but_Delicious_Sushisについて、Changeable_Sushiに含まれるsushiと順番に交換して合計点を求める

max_point = selected_Sushis_Point + num_selected_Groups**2

#p "selected_Sushis_Point: #{selected_Sushis_Point}, num_selected_Groups: #{num_selected_Groups}, max_point: #{max_point}"
#p "Unselected_but_Delicious_Sushis: #{Unselected_but_Delicious_Sushis}"
#p "Changeable_Sushi: #{Changeable_Sushi}"

for i in 0...Unselected_but_Delicious_Sushis.size do
	break if Changeable_Sushi.size <= i

	unselected_sushi = Unselected_but_Delicious_Sushis[i]
	next if selected_Groups_Set.include?(unselected_sushi[0])

	changeable_sushi = Changeable_Sushi[i]

	num_selected_Groups += 1
	selected_Sushis_Point += unselected_sushi[1] - changeable_sushi
	new_point = selected_Sushis_Point + num_selected_Groups**2

	max_point = [max_point, new_point].max
	#p "unselected_sushi: #{unselected_sushi}"
	#p "changeable_sushi: #{changeable_sushi}"
	#p "num_selected_Groups: #{num_selected_Groups}"
	#p "max_point: #{max_point}"
end

p max_point
