def satisfaction(choice)
  point = choice.inject { |prev, sushi| prev + sushi[:score] }
  neta_count = choice.map { |sushi| sushi[:neta] }.uniq.size
  point + neta_count**2
end

n, k = gets.split.map(&:to_i)
$sushis = (1..n).map do |i|
  sushi = gets.split
  { id: i, neta: sushi[0], score: sushi[1] }
end
# $netas = $sushis.map { |h| h[:neta] }.uniq

def improve_choice(choice)
  select_netas = choice.map { |h| h[:neta] }.uniq
  duplicated_sushis = choice.group_by { |h| h[:neta] }.select { |_, v| v.size > 1 }.map { |_, v| { id: v[:id], score: v[:score] } }
  id = duplicated_sushis.sort_by { |h| h[:score] }[0][:id]
  $sushis.each do  |sushi|
    if select_netas.include? sushi[:neta]
      new_sushi = sushi
      break
    end
  end
  choice.map { |v| (v[:id] == id) ? new_sushi : v }
end

score_sort_sushi = $sushis.sort_by { |sushi| sushi[:score] }
choice = (0...k).map { |i| score_sort_sushi[i] }

satisfaction_old = satisfaction choice
satisfaction_new = 0
while satisfaction_new > satisfaction_old
  satisfaction_old = satisfaction_new
  choice = improve_choice choice
  satisfaction_new = satisfaction choice
end

puts satisfaction_old
