de = false
require 'set'; require 'prime'
INF=Float::INFINITY; MOD=10**9+7
n,k = gets.chomp.split.map(&:to_i)
h = {}
td = []
n.times do
  tmp = gets.split.map(&:to_i)
  td.push tmp
  t,d = tmp
  h[t] ||= []
  h[t].push d
end

current = 0

k_values = {}
used_t = Set.new
td.sort_by{|t,d| -d}.slice(0,k).each do |t,d|
  k_values[t] ||= []
  k_values[t].push d
  current += d
  used_t.add t
end
k_values_to_remove = []
k_values = k_values.each do |k,values|
  k_values_to_remove += values.sort.slice(0, values.size-1)
end
k_values_to_remove.sort!
p ['h',h] if de
p ['k_values_to_remove', k_values_to_remove] if de

max_values = []
h.each do |t,d|
  next if used_t.include? t
  max_values.push d.max
end
p ['max_values', max_values] if de

kcount = used_t.size

p current if de
ans = current + kcount ** 2
max_values.sort.reverse_each do |max_v|
  k_values_to_remove_min = k_values_to_remove.shift
  break if k_values_to_remove_min.nil?
  kcount += 1
  current = current - k_values_to_remove_min + max_v
  tmp = current + kcount ** 2
  ans = tmp if ans < tmp
  # p [k_values_to_remove, kcount**2, current] if de
end

puts ans
