N, K = gets.split.map(&:to_i)
TDs = readlines.map{|l| l.split.map(&:to_i)}

tds = TDs.sort_by{|t, d| -d}
dns, uds = tds.take(K).reverse, tds.drop(K)
ts = dns.each_with_object(Hash.new(0)){|(t, d), h| h[t] += 1}
ks =ts.keys.size
pt = dns.map(&:last).inject(:+) + ks**2
ans = pt
(ks + 1 .. [K, tds.map(&:first).uniq.size].min).each do |a|
  t, d = dns.delete_at(dns.index{|t, d| ts[t] > 1})
  ts[t] -= 1
  t1, d1 = uds.delete_at(uds.index{|t, d| ts[t].zero?})
  ts[t1] += 1
  pt = pt - d + d1 + 2*a - 1
  ans = pt if pt > ans
end
puts ans