n, k = gets.split.map(&:to_i)
sushi = Hash.new { |h, k| h[k] = [] }

s_0 = []
s_1 = []

n.times do
  t, d = gets.split.map(&:to_i)
  sushi[t] << d
end
sushi.values.each do |arr|
  arr.sort!.reverse!
  arr.each_with_index do |a, i|
    if i == 0
      s_1 << a
    else
      s_0 << a
    end
  end
end
s_0.sort_by! { |d| -d }
s_1.sort_by! { |d| -d }

n_0 = s_0.size
n_1 = s_1.size

tmp = 0
sum_0 = [0].concat(s_0.map { |si| tmp += si })
tmp = 0
sum_1 = [0].concat(s_1.map { |si| tmp += si })

ans = 0
(k + 1).times do |i|
  next if i == 0
  # s_1 からi個とる
  next if n_1 < i
  sum = (sum_1[i] - sum_1[0]) + i * i
  if i < k
    # s_0 からk-i個とる
    next if n_0 < k - 1
    sum += (sum_0[k - i] - sum_0[0])
  end
  ans = sum if sum > ans
  # p [i, s_1[0, i].concat(s_0[0, k - i]), sum]
end

p ans
