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

tds = TDs.sort_by{|t, d| -d}
p1, r1 = tds.take(K), tds.drop(K)
th = p1.each_with_object(Hash.new(0)){|(t, d), h| h[t] += 1}
k0 = tds.map(&:first).uniq.size
k1 = th.keys.size
n = [k0, K].min - k1
p2 = p1.select{|t, d| th[t] > 1}.group_by{|t,d| t}.flat_map{|k, v| v.map(&:last).drop(1).reverse}.sort.take(n)
r2 = r1.select{|t, d| th[t].zero?}.group_by{|t, d| t}.flat_map{|k, v| v.map(&:last).take(1)}.sort.reverse.take(n)
pt1 = p1.inject(0){|s, (t, d)| s + d} + k1*k1
puts (k1 + 1 .. k1 + n).each_with_object([pt1]){|i, a| a << a.last -  p2.shift + r2.shift + 2*i - 1}.max