require 'set'
(n,k),*td=$<.map{|s|s.split.map &:to_i}

td.sort_by!{|t,d|[-d,t]}
tkn=td[0,k]
s=tkn.reduce(0){|m,(t,d)|m+d}
knd=Set[*tkn.map{|t,d|t}]
my=td[k..-1]
hs={}
g=tkn.group_by{|t,d|hs[t] || !(hs[t]=true)}
ds=g[true]||[]
s+=knd.size**2
r=s
loop {
  break if ds.empty?
  my.delete_if{|t,d|knd.member?(t)}
  break if my.empty?
  t1,d1=my.shift
  knd.add(t1)
  t2,d2=ds.pop
  s=s+d1-d2+knd.size*2-1
  r=[r,s].max
}
p r
