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!.reverse!
yowai_sushi.sort!.reverse!

intstrong = [0]
intyowai = [0]

accum = 0
strong.each do |x|
  accum += x
  intstrong << accum
end

accum = 0
yowai_sushi.each do |x|
  accum += x
  intyowai << accum
end

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

p max
