(n,k),*td=$<.map{|s|s.split.map &:to_i}
td.sort_by!{|t,d|[-d,t]}
h=[]
v=[]
x=s=0
td[0,k].map{|t,d|h[t]?v<<d:x+=1;h[t]=1;s+=d}
r=s+=x**2
td[k..-1].map{|t,d|v.empty?||h[t]||(r<s+=d-v.pop-1+2*x+=1)&&r=s;h[t]=1}
p r