require 'set'

n, k = gets.strip.split.map(&:to_i)
td = readlines.map {|line| line.strip.split.map(&:to_i) }

grouped_td = td.group_by(&:first)

sushi_max = grouped_td.map {|t, arr| [t, arr.map(&:last)] }.map {|t, arr| [t, arr.sort.reverse] }

selected = []
unselected = []
sushi_max.each do |k, arr|
  selected.push( [1,arr.shift] )
  unselected += arr.map {|e| [0, e] }
end

selected = selected.sort_by(&:last).reverse
unselected = unselected.sort_by(&:last).reverse

all = (selected + unselected).sort_by(&:last).reverse

selected = all.take(k)
unselected = all[k...n]

mobile = []
in_result = 0
selected.each do |t, d|
  if !t.zero?
    in_result+=1
  else
    mobile.push([t, d])
  end
end

current_score = selected.map(&:last).inject(:+)

result = current_score + in_result**2

if n==k
  p result
  exit
end

unselected.each do |t, d|
  next if t.zero?

  swap_target = mobile.pop
  break if swap_target.nil?
  current_score -= swap_target.last + d
  current_score += d
  in_result+=1
  current_result = current_score + in_result**2

  result = current_result if current_result > result
end

p result

