class Heap
  attr_reader :size

  def initialize
    @heap = []
    @size = 0
  end

  def add(n)
    i = @size
    while i > 0 do
      parent_index = (i - 1) / 2
      break if n >= @heap[parent_index]

      @heap[i] = @heap[parent_index]
      i = parent_index
    end

    @heap[i] = n
    @size += 1
  end

  def pop
    min = @heap[0]
    @size -= 1
    n = @heap[@size]
    i = 0
    while i * 2 + 1 < @size do
      child_index1 = i * 2 + 1
      child_index2 = i * 2 + 2
      if child_index2 < @size && @heap[child_index2] < @heap[child_index1]
        child_index1 = child_index2
      end
      break if @heap[child_index1] >= n

      @heap[i] = @heap[child_index1]
      i = child_index1
    end
    @heap[i] = n
    min
  end

  def min; @heap[0] end
  def values; @heap.first(@size) end
  def inspect; values end
end

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

sushi_heaps = Array.new(N + 1) { Heap.new }
K.times.map { sushis.shift }.each do |sushi|
  sushi_heaps[sushi[:type]].add(sushi[:oisisa])
end
current_types_count = sushi_heaps.count { |sushi_heap| sushi_heap.size > 0 }

def calc_points(sushi_heaps)
  sushi_heaps.count { |sushi_heap| sushi_heap.size > 0 } ** 2 + sushi_heaps.inject(0) { |sum, sushi_heap| sum + sushi_heap.values.inject(:+).to_i }
end

max_points = calc_points(sushi_heaps)
current_types_count.upto(types_count) do
  min_i = nil
  min_value = Float::INFINITY
  sushi_heaps.each_with_index do |sushi_heap, i|
    if sushi_heap.size > 1 && sushi_heap.min < min_value
      min_i = i
      min_value = sushi_heap.min
    end
  end
  break if min_i.nil?

  sushi_heaps[min_i].pop
  sushi = sushis.shift
  while sushi_heaps[sushi[:type]].size > 0
    sushi = sushis.shift
  end
  sushi_heaps[sushi[:type]].add(sushi[:oisisa])

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

puts max_points