Item = Struct.new(:kind, :value) do 
  def inspect
    "#{value}(#{kind})"
  end
end
N,K = gets.split.map(&:to_i)
T = N.times.map{Item.new(*gets.split.map(&:to_i))}
T.sort_by!(&:value)
S = T.pop(K)

X = S.each_with_object(Hash.new(0)) do |v,o|
  o[v.kind] += 1
end

loop do
  S.sort_by!(&:value)
  T.sort_by!{|v| -v.value }
  
  break unless S.each_index.find do |i|
    e = S[i]
    j = T.index do |e_|
      X[e_.kind] > 1 && e_.value + X.size * 2 + 1 - e.value > 0 
    end
    if j
      e_ = T[j]
      T[j] = e
      S[i] = e_
      X[e.kind] -= 1
      X[e_.kind] ||= 0; X[e_.kind] += 1
      swapped = true
    end
  end
end

puts S.map(&:value).sum + X.size ** 2