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

grouped_td = td.group_by(&:first)
neta_count = grouped_td.keys

neta_max = grouped_td.map {|t, arr| [t, arr.map(&:last)] }.map {|t, arr| [t, arr.max] }.sort_by(&:last).reverse
#p neta_count
#p grouped_td
#p neta_max

targets = neta_max
if k < neta_count.length
  targets = neta_max[0...k]
end

targets.each do |t|
  td.delete_at(td.index(t))
end

td = td.sort_by(&:last).reverse

def point(sushi)
  points = sushi.group_by(&:first).map {|_, v| v.map(&:last).inject(:+) }
  points.inject(:+) + points.length**2
end

result = point(targets)

(n-targets.length).times do
  tmp_targets = targets.dup
  tmp_targets.push(td.shift)
  tmp_targets = tmp_targets.sort_by(&:last)
  tmp_targets.shift
  tmp_result = point(tmp_targets)
  result = tmp_result if result < tmp_result
  break if result >= tmp_result
  targets = tmp_targets
end

p result
#p targets


