class SkewHeapNode
  attr_accessor :element, :left, :right, :parent
  def initialize(element, left = nil, right = nil)
    @element = element
    @left = left
    @right = right  
    @parent = nil
  end
end

class SkewHeap
  attr_reader :size, :root
  def initialize
    @root = nil
    @size = 0
    @position = {}
    @id = 0
  end

  def add(element)
    @id += 1
    @size += 1
    node = SkewHeapNode.new(element)
    @position[@id] = node
    @root = merge(@root, node)
    @id
  end

  def top
    @root ? @root.element : nil
  end

  def pop
    return nil if @size==0
    @size -= 1
    element = @root.element
    @root = merge(@root.left, @root.right)
    @root.parent = nil if @root
    element
  end

  def change_key(target_id, new_element)
    node = @position[target_id]
    return nil unless node
    if heap_order_property_satisfied?(node, new_element)
      node.element = new_element
    else
      temp = merge(node.left, node.right)
      temp.parent = node.parent if temp
      if node.parent
        if node.parent.left == node
          node.parent.left = temp
        else
          node.parent.right = temp
        end
      else
        @root = temp
      end
      node.element = new_element
      node.left = nil
      node.right = nil
      node.parent = nil

      @root = merge(@root, node)
      @root.parent = nil if @root
    end
    self
  end

  def empty?
    @size == 0
  end

  alias :push :add
  alias :<< :add
  alias :length :size

private
  def merge(p, q)
    return p if q.nil?
    return q if p.nil?
    p, q = q, p if p.element > q.element
    q.parent = p
    p.right = merge(p.right, q)
    p.right, p.left = p.left, p.right
    p
  end

  def heap_order_property_satisfied?(node, new_element)
    if node.parent
      return false if node.parent.element > new_element
    end
    if node.left
      return false if node.left.element < new_element
    end
    if node.right
      return false if node.right.element < new_element
    end
    true
  end
end

class Sushi
  attr_accessor :t, :d
  def initialize(t,d)
    @t,@d=t,d
  end

  def <(other)
    @d<other.d
  end

  def >(other)
    @d>other.d
  end
end

n,k=gets.split.map(&:to_i)
sushi=n.times.map{gets.split.map(&:to_i)}.sort_by(&:last).
  reverse.map{|arg|Sushi.new(*arg)}
heap=SkewHeap.new
tops=[]

topping_num=0
topping_flag=Array.new(n+1)
total_deliciousness=0
k.times{|i|
  s=sushi[i]
  total_deliciousness+=s.d
  if topping_flag[s.t]
    heap << s
  else
    topping_flag[s.t]=true
    topping_num+=1
    tops << s
  end
}
ans=total_deliciousness+topping_num**2

k.upto(n-1){|i|
  break if heap.empty?
  s=sushi[i]
  next if topping_flag[s.t]
  topping_flag[s.t]=true
  topping_num+=1
  total_deliciousness+=s.d
  tops << s
  u=heap.pop
  total_deliciousness-=u.d
  satisfaction=total_deliciousness+topping_num**2
  ans=satisfaction if satisfaction>ans 
}

puts ans