class PriorityQueue
  def initialize(&comp)
    @heap = []
    @node_num = 0
    if !block_given?
      @comp = Proc.new { |x, y| x <= y }
    else
      @comp = comp
    end
  end

  attr_reader :heap

  def push(x)
    current_node_num = @node_num
    @node_num += 1
    while current_node_num > 0
      parent_node_num = (current_node_num - 1) / 2
      break if @comp.call(@heap[parent_node_num], x) # 逆転してないなら抜ける
      # 親ノードを下ろして自分を上に
      @heap[current_node_num] = @heap[parent_node_num]
      current_node_num = parent_node_num
    end
    @heap[current_node_num] = x
  end

  alias_method(:<<, :push)

  def pop
    # 最(小|大)値
    ret = @heap[0]
    # 根にもってくる値
    @node_num -= 1
    x = @heap[@node_num]
    # 根から下ろしていく
    i = 0
    while (a = i * 2 + 1) < @node_num
      # 子どうしを比較
      b = a + 1
      a = b if b < @node_num && @comp.call(@heap[b], @heap[a])
      break unless @comp.call(@heap[a], x)
      @heap[i] = @heap[a]
      i = a
    end
    @heap[i] = x
    return ret
  end

  def get
    @node_num == 0 ? nil : @heap[0]
  end

  def empty?
    return get.nil?
  end
end

n, k = gets.split.map(&:to_i)
sushi = PriorityQueue.new { |x, y| x[1] > y[1] }
ts = []
all_kinds = 0 # 全部で何種類の寿司
n.times do
  t, d = gets.split.map(&:to_i)
  all_kinds += 1 if ts[t].nil?
  sushi << [t, d]
end

ans = 0

used = Hash.new(0)
kinds = 0
sum = 0
ss = Hash.new { |h, k| h[k] = PriorityQueue.new }
k.times do
  t, d = sushi.pop
  kinds += 1 if used[t] == 0
  used[t] += 1
  sum += d
  ss[t] << d
end
ans = sum + kinds * kinds

# p ss
# p ans

cnt = used.keys.size
while cnt < all_kinds
  cnt += 1
  # # 追加する寿司
  tmp = sushi.pop
  while used[tmp[0]] != 0
    tmp = sushi.pop
    if tmp.nil?
      puts ans
      exit
    end
  end
  # 削除する寿司
  # used[t] >= 2 であるもののうちおいしさが最小のもの
  remove_t = -1
  mn = 1e10
  ss.each do |t, ds|
    dmin = ds.get
    next if t < 2 || dmin.nil?
    remove_t = t if mn > dmin
  end
  break if remove_t == -1
  remove_d = ss[remove_t].pop
  sum += (tmp[1] - remove_d)
  ss[tmp[0]] << tmp[1]
  used[remove_t] -= 1
  used[tmp[0]] += 1
  cnt += 1
  ans = [ans, sum + cnt * cnt].max
end

# p ss
p ans
