N, K = gets.split.map(&:to_i)
sushis = N.times.map { gets.split.map(&:to_i) }.sort_by! { |sushi| -sushi[1] }
types_count = sushis.map { |sushi| sushi[0] }.uniq.size
current_sushis = sushis[0...K]
count_by_type = Array.new(N + 1, 0)
current_sushis.each { |sushi| count_by_type[sushi[0]] += 1 }
# p sushis, current_sushis

types_count = count_by_type.count { |c| c > 0 }
max_points = types_count ** 2 + current_sushis.inject(0) { |sum, sushi| sum + sushi[1] }

K.upto(N-1) do |i|
  next if count_by_type[sushis[i][0]] > 0
  hit = false
  (K-1).downto(0) do |j|
    if count_by_type[current_sushis[j][0]] > 1
      count_by_type[current_sushis[j][0]] -= 1
      current_sushis[j] = sushis[i]
      count_by_type[current_sushis[j][0]] += 1
      types_count += 1
      hit = true
      break
    end
  end
  break unless hit

  max_points = [max_points, types_count ** 2 + current_sushis.inject(0) { |sum, sushi| sum + sushi[1] }].max
  # p current_sushis, max_points
end

puts max_points