require 'set'

N, K = gets.split(' ').map(&:to_i)
td_list = N.times.map { gets.split(' ').map(&:to_i) }

sorted_td_list = td_list.sort_by { |(_, d)| -d }
current_td_list = sorted_td_list.take(K)
t_to_size = Hash.new(0).tap do |h|
  current_td_list.each { |k, _| h[k] += 1 }
end
t_set = Set.new(t_to_size.keys)
max_score = current_td_list.reduce(0) do |acc, (_, d)|
  acc + d
end + t_set.size ** 2
current_score = max_score

deleted_i = K - 1
rest_sorted_td_list = sorted_td_list.drop(K)
rest_sorted_td_list.each.with_index do |(t, d), i|
  break if t_set.size >= K
  next if t_set.include?(t)
  while deleted_i >= 0
    dt, _ = sorted_td_list[deleted_i]
    break if t_to_size[dt] >= 2
    deleted_i -= 1
  end
  break unless deleted_i >= 0
  t_set.add(t)
  dt, dd = sorted_td_list[deleted_i]
  t_to_size[dt] -= 1
  t_to_size[t] = 1
  current_score = current_score + (d + (t_set.size ** 2)) - (dd + ((t_set.size - 1) ** 2))
  max_score = current_score if max_score < current_score
end
puts max_score
