DBG = true
n,k = gets.split.map{|x| x.to_i}
td = []
for i in 0...n
  tt,dd = gets.split.map{|x| x.to_i}
  td << [tt,dd]
end

# おいしさでソート
td.sort_by!{|z| -z[1]}
if DBG
  print td
  puts ""
end

# ネタ種類ごと
tt = td.map{|z| z[0]}.uniq
h = {}
hmax = {}
for t in tt
  h[t] = []
  hmax[t] = 0
end
for i in 0...n
  t = td[i][0]
  d = td[i][1]
  h[t] << d
  hmax[t] = d if d > hmax[t]
end
if DBG
  print h
  puts ""
  print hmax
  puts ""
end

# おいしさの上位K個
donly = td[0,k].map{|z| z[1]}.inject(:+)
puts "#{donly}" if DBG

# そこに入らないネタ(t)の上位各１個ずつ
usedts = td[0,k].map{|z| z[0]}.uniq
unusedts = tt - usedts
unusedtval = unusedts.map{|t| hmax[t]}
unusedtval.sort_by!{|v| -v}

# 使った寿司
usedset = {}
for t in tt
  usedset[t] = []
end
for td0 in td[0,k]
  t = td0[0]
  d = td0[1]
  usedset[t] << d
end

# 各ネタ種類の、最大値のものをマーク（入れ替えない）
marked = {}
for i in 0...n
  t = td[i][0]
  d = td[i][1]
  if !marked.has_key?(t) && d == hmax[t]
    marked[t] = i
  end
end
if DBG
  print "marked: "
  print marked
  puts ""
  print "usedts: "
  print usedts
  puts ""
  print "unusedtval: "
  print unusedtval
  puts ""
end

# おいしさが下のから１個ずつ、違う種類に入れ替えていく
nkind = usedts.size
maxval = donly + nkind*nkind
curval = donly
(k-1).downto(1) { |i|
  break if unusedtval.empty?
  t = td[i][0]
  d = td[i][1]
  if i != marked[t]
    nkind += 1
    v = unusedtval.shift
    curval += v - d
    curvalx = curval + nkind*nkind
    maxval = curvalx if curvalx > maxval
  end
}
puts "#{maxval}"
