n, k = gets.split.map(&:to_i)

# sushi[kind][...]
sushi = {}
n.times do |i|
  t, d = gets.split.map(&:to_i)
  sushi[t] = [] unless sushi.include?(t)
  sushi[t] << d
end

sushi.each do |k, s|
  s.sort_by! {|n| -n }
end

strong = []
yowai_sushi = []
sushi.each do |k, v|
  strong << v[0]
  v.shift
  yowai_sushi += v
end

strong.sort_by! {|n| -n}

intstrong = [0]
intyowai = [0]

strong.each do |x|
  intstrong << (x + intstrong[-1])
end

yowai_sushi.each do |x|
  intyowai << (x + intyowai[-1])
end

max = 0
([k, strong.size].min+1).times do |t|
  tmp = intstrong[t]
  if k - t < intyowai.size
    tmp += intyowai[k - t]
    max = [max, tmp + t*t].max
  end
end

p max
