N, K = gets.split.map(&:to_i)
sushis = []
N.times do
  t, d = gets.split.map(&:to_i) # t: ネタ, d: おいしさ
  sushis << {
    type: t,
    oisisa: d,
  }
end

sushis.sort_by! { |sushi| sushi[:oisisa] }
types_count = sushis.map { |sushi| sushi[:type] }.uniq.size

current_sushis = K.times.map { sushis.pop }
current_types_count = current_sushis.map { |sushi| sushi[:type] }.uniq.size

def calc_points(sushis)
  sushis.map { |sushi| sushi[:type] }.uniq.size ** 2 + sushis.inject(0) { |sum, sushi| sum + sushi[:oisisa] }
end

count_by_type = Array.new(N + 1, 0)
current_sushis.each { |sushi| count_by_type[sushi[:type]] += 1 }

max_points = calc_points(current_sushis)
current_types_count.upto(types_count) do |ii|
  min_i = nil
  min_value = Float::INFINITY
  current_sushis.each_with_index do |sushi, i|
    if count_by_type[sushi[:type]] > 1 && min_value > sushi[:oisisa]
      min_i = i
      min_value = sushi[:oisisa]
    end
  end
  break if min_i.nil?

  deleted_sushi = current_sushis.delete_at(min_i)
  count_by_type[deleted_sushi[:type]] -= 1
  sushi = sushis.pop
  break if sushi.nil?

  while count_by_type[sushi[:type]] > 0
    sushi = sushis.pop
  end
  current_sushis << sushi
  count_by_type[sushi[:type]] += 1

  max_points = [max_points, calc_points(current_sushis)].max
end

puts max_points