N,K = gets.split.map(&:to_i)

greedy = (0..N-1).map{gets.split.map(&:to_i)}.sort_by{|e| -e[1]}

kiso = 0
set = [] #削除候補
neta = Hash.new{|h,k| h[k] = false}

K.times do |i|
  kiso += greedy[i][1]

  if neta[greedy[i][0]]
    set << greedy[i][1]
  else
    neta[greedy[i][0]] = true
  end

end

# p set
# p neta

deletable = -1

syurui = neta.count{|k,v| v }
ans = kiso + syurui*syurui

K.upto(N-1) do |i|
  t, d = greedy[i]
  next if neta[t]
  break if set.empty?

  kiso += d - set.pop
  syurui += 1
  tmp = kiso + syurui**2
  neta[t] = true

  # puts "kiso=#{kiso}"
  # puts "syurui=#{syurui}"
  # puts "tmp=#{tmp}"

  ans = tmp if tmp > ans
end

puts ans
