class SkewHeap
  def initialize(rev = nil)
    @rev = rev
  end
  def push(k)
    @root = meld(@root, Node.new(k))
  end
  def top
    @root.key
  end
  def empty?
    @root == nil
  end
  def pop
    key = @root.key
    @root = meld(@root.lchild, @root.rchild)
    key
  end
  def meld(lhs, rhs)
    return lhs unless rhs
    return rhs unless lhs
    lhs, rhs = rhs, lhs unless lhs.key < rhs.key
    lhs, rhs = rhs, lhs if @rev && lhs.key < rhs.key
    lhs.rchild = meld(lhs.rchild, rhs)
    lhs.lchild, lhs.rchild = lhs.lchild, lhs.rchild
    lhs
  end
  class Node
    attr_accessor :key, :lchild, :rchild
    def initialize(k)
      @key = k
    end
  end
end

class Sushi
  include Comparable
  attr_accessor :t,:d
  def initialize(t,d)
    @t,@d=t,d
  end
  def <=>(o)
    @d!=o.d ? @d<=>o.d : @t<=>o.t
  end
end

N,K=gets.split.map(&:to_i)
S=N.times.map{gets.split.map(&:to_i)}
H=Hash.new{|h,k|h[k]=0}
Q=SkewHeap.new
ans=s=k=x=0
S.sort{|l,r|r[1]<=>l[1]}.each do |t, d|
  if k<K
    Q.push(Sushi.new(t,d))
    s+=d
    s-=x*x
    k+=1
    x+=1 if H[t].zero?
    s+=x*x
    H[t]+=1
  else
    until Q.empty?
      q=Q.pop
      next if H[q.t]==1
      next if q.t==t
      H[q.t]-=1
      s-=q.d
      Q.push(Sushi.new(t,d))
      s+=d
      s-=x*x
      x+=1 if H[t].zero?
      s+=x*x
      H[t]+=1
      break
    end
  end
  ans=[ans,s].max
end
p ans
