N, K = gets.split.map(&:to_i)
sushi = {}
N.times do
  t, d = gets.split.map(&:to_i)
  sushi[t] ||= []
  sushi[t] << d
end

maxes = []
others = []

sushi.each_value do |v|
  v.sort!
  maxes << v.pop
  others.concat(v)
end


maxes = maxes.sort_by! {|m| -m}
others = others.sort_by! {|o| -o}

# p maxes, others

sum_max = [0]
maxes.each do |m|
  sum_max << sum_max[-1] + m
end
sum_other = [0]
others.each do |o|
  sum_other << sum_other[-1] + o
end

# p sum_max, sum_other

max = 0
1.upto([K, maxes.size].min) do |kind|
  tmp = sum_max[kind] + sum_other[K-kind].to_i + kind**2
  if tmp > max
    max = tmp
  end
end

p max
