def score(t_num,n,k,sushi)
  ret=t_num**2
  flag=Array.new(n+1)
  sushi.each{|t,d|
    if t_num==k
      unless flag[t]
        flag[t]=true
        t_num-=1
        k-=1
        ret+=d
      end
    else
      ret+=d
      k-=1
      unless flag[t]
        t_num-=1
        flag[t]=true
      end
    end
    break if k==0
  }
  ret
end

n,k=gets.split.map(&:to_i)
sushi=n.times.map{gets.split.map(&:to_i)}
topping_flag=Array.new(n+1)
topping_num=0
sushi.each{|t,d|
  unless topping_flag[t]
    topping_num+=1
    topping_flag[t]=true
  end
}
sushi.sort_by!(&:last)
sushi.reverse!

l=1
r=topping_num
max=[l,r].map{|t|score(t,n,k,sushi)}.max
500.times{
  m1=(2*l+r)/3
  m2=(l+2*r)/3
  s1=score(m1,n,k,sushi)
  s2=score(m2,n,k,sushi)
  if s1<s2
    l=m1
    max=[max,s2].max
  else
    r=m2
    max=[max,s1].max
  end
}
puts max