require 'set'

n, k = gets.strip.split.map(&:to_i)
ss = []
n.times do
  ss << gets.strip.split.map(&:to_i)
end

def calc(xs)
  pt = xs.map{|x| x[1]}.inject(:+)
  kind = Set.new(xs.map{|x| x[0]}).size
  pt += kind * kind
  pt
end

ss.sort! {|a, b| a[1] <=> b[1]}
cand = ss[0...k]
remaining = ss[k...n]
max_pt = calc(cand)
ways = Set.new; ways << cand
loop do
  kind = Hash.new(0)
  cand.map{|x| kind[x[0]] += 1}
  neta_min = cand.min_by      {|x| (kind[x[0]] > 1) ? x[1] :  10000000}
  neta_max = remaining.max_by {|x| (kind[x[0]] <= 1) ? x[1] : -10000000}
  cand -= [neta_min]; remaining += [neta_min]
  cand += [neta_max]; remaining -= [neta_max]
  break if ways.include? cand
  ways << cand
  pt = calc(cand)
  if pt > max_pt then
    max_pt = pt
  end
end
puts max_pt