require 'set'
INF = 1 << 60

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

def score(t_to_dlist)
  t_to_dlist.reduce(0) { |acc, (_, dlist)| acc + dlist.reduce(&:+) } +
  t_to_dlist.keys.size ** 2
end

def t_of_min_d(t_to_dlist)
  target_t = nil
  min = INF
  t_to_dlist.each do |(t, dlist)|
    next unless dlist.size >= 2
    d = dlist.last
    if d < min
      min = d
      target_t = t
    end
  end
  target_t
end

sorted_td_list = td_list.sort_by { |(_, d)| -d }
t_to_dlist =
  sorted_td_list.take(K).group_by(&:first).tap do |t_to_tdlist|
    t_to_tdlist.keys.each do |t|
      td_list = t_to_tdlist[t]
      t_to_tdlist[t] = td_list.map { |(_, d)| d }
    end
  end
t_set = Set.new(t_to_dlist.keys)
rest_sorted_td_list = sorted_td_list.drop(K)

max_score = score(t_to_dlist)
current_score = max_score
rest_sorted_td_list.each do |(t, d)|
  break if t_set.size >= K
  next if t_set.include?(t)
  t2 = t_of_min_d(t_to_dlist)
  break unless t2
  t_set.add(t)
  dlist = t_to_dlist[t2]
  d2 = dlist.pop
  if dlist.empty?
    t_to_dlist.delete(t2)
    t_set.delete(t2)
  end
  t_to_dlist[t] = [d]
  current_score = current_score + (d + (t_set.size ** 2)) - (d2 + ((t_set.size - 1) ** 2))
  max_score = current_score if max_score < current_score
end
puts max_score
