def main()
  n, k = gets.chomp.strip.split(' ').map(&:to_i)
  t = []
  d = []
  exist_kind_with_d = []
  exist_kinds = []
  sum = 0
  for i in 0..(n-1) do
    t[i], d[i] = gets.chomp.strip.split(' ').map(&:to_i)
  end
  max_number_of_kind = (t.uniq.length > k)? k : t.uniq.length
  
  for i in 1..k do
    exist_kind_with_d_max = (exist_kind_with_d.length > 0) ? exist_kind_with_d.max : 0
    d_max = d.max
    decrease_of_sum = max_number_of_kind ** 2 - (max_number_of_kind -1) ** 2
    if (exist_kind_with_d_max - decrease_of_sum) > d_max
      sum += exist_kind_with_d_max
      max_number_of_kind -= 1
      cur_index = exist_kind_with_d.index(exist_kind_with_d_max)
      exist_kind_with_d.delete_at(cur_index)
    else
      sum += d_max
      cur_index = d.index(d_max)
      cur_kind = t[cur_index]
      exist_kinds << cur_kind
      d.delete_at(cur_index)
      t.delete_at(cur_index)
      del_indexes = []
      t.each_with_index do |value, index|
        if value == cur_kind
          exist_kind_with_d << d[index]
          del_indexes << index
        end
      end
      del_indexes.reverse.each do |index|
        d.delete_at(index)
        t.delete_at(index)
      end
    end
  end
  sum += exist_kinds.length ** 2
  puts "#{sum}"
end
main