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)
d_sum = current_td_list.reduce(0) do |acc, (_, d)|
  acc + d
end
max_score = d_sum + t_set.size ** 2

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
    break if t_to_size[sorted_td_list[deleted_i][0]] >= 2
    deleted_i -= 1
  end
  break if deleted_i < 0
  t_set.add(t)
  dt, dd = sorted_td_list[deleted_i]
  t_to_size[dt] -= 1
  t_to_size[t] = 1
  d_sum += d - dd
  current_score = d_sum + t_set.size ** 2
  max_score = current_score if max_score < current_score
end
puts max_score
