# https://atcoder.jp/contests/abc116/tasks/abc116_d

Sushi = Struct.new(:t, :d, :max)

N, K = gets.split.map(&:to_i)
vs = Array.new(N)
N.times do |i|
  vs[i] = Sushi.new(*gets.split.map(&:to_i), false)
end

vs
.group_by { |v| v.t }
.each do |k, ws|
  ws.sort_by { |w| w.d }.last.max = true
end

xs, os = vs.partition { |v| v.max }.map { |vs| vs.sort_by { |v| -v.d }}

xacc = xs.each_with_object([0]) { |x, arr| arr.push(arr.last + x.d) }
oacc = os.each_with_object([0]) { |o, arr| arr.push(arr.last + o.d) }

ans = 0
1.upto(K) do |i|
  next unless xacc[i] && oacc[K - i]
  ans = [ans, xacc[i] + oacc[K - i] + i * i].max
end

puts ans
