require 'set'
n, k = gets.strip.split.map(&:to_i)
td = readlines.map {|line| line.strip.split.map(&:to_i) }

td.sort_by {|td| td.last*-1 }

selected = td[0, k]
unselected = td[k, n]

current_kinds = Set.new(selected.map(&:first))
current_score = selected.map(&:last).inject(:+)
max = current_score + current_kinds.size**2

if n==k
  p max
  exit
end

dup_set = Set.new
dups_in_selected = []
selected.each do |t, d|
  if dup_set.include?(t)
    dups_in_selected << [t,d]
  else
    dup_set << t
  end
end

unselected.each do |t, d|
  next if current_kinds.include?(t)
  removed = dups_in_selected.pop
  break if removed.nil?
  current_score -= removed.last
  current_score += d
  current_kinds << t
  tmp_max = current_score + current_kinds.size**2
  max = tmp_max if tmp_max > max
end

p max




