(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}
x=tkn.map{|t,d|t}.uniq.size
knd=[]
ds=[]
tkn.map{|t,d|
  ds << [t,d] if knd[t]
  knd[t]=true
}
my=td[k..-1]
s+=x**2
r=s
i=0
loop {
  break if ds.empty?
  while my[i]&&knd[my[i][0]]
    i+=1
  end
  break if my.empty?
  t1,d1=my[i]
  knd[t1]=true
  t2,d2=ds.pop
  s=s+d1-d2+x*2-1
  r=[r,s].max
}
p r
