Item = Struct.new(:kind,:value)

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

T = N.times.map{Item.new(*gets.split.map(&:to_i)) }.sort_by{|v| -v.value}
S = T.shift(K) # take higeher k items
S.sort_by(&:value) # sort asc

T.reverse # sort by desc
used = {}

S.each{|v| used[v.kind] ||= 0; used[v.kind] += 1 }

S_ = S.map do |e|
  next e if used[e.kind] == 1
  
  T.reject!{|v| used[v.kind] }
  e_ = T.find{|v| !used[v.kind] && (v.value + used.size * 2 + 1 - e.value > 0) } || e
  
  if e != e_
    T.delete(e_)
    used[e_.kind] = 1
    used[e.kind] -= 1
  end
  
  e_
end

puts S_.map(&:value).inject(&:+) + used.size ** 2
