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)
used = Array.new(K) { false }
(0...K).each { |i| used[i] = true }
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

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)
  deleted_i = nil
  (P + i).downto(0) do |j|
    next unless used[n]
    t, d = sorted_td_list[n]
    if t_to_size[t] >= 2
      deleted_i = j
      break
    end
  end
  break unless deleted_i
  used[deleted_i] = false
  used[i + K] = true
  t_set.add(t)
  dt, dd = sorted_td_list[deleted_i]
  t_to_size[dt] -= 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
