n, k = gets.split.map(&:to_i)
l = Array.new(10){ Array.new }
n.times do
  p, q = gets.split.map(&:to_i)
  l[q-1] << p
end
l.each{|arr| arr.sort!.reverse! }
dp = Array.new(2){ Array.new(n, 0) }
10.times do |i|
  (0..k).each do |j|
    dp[i%2][j] = [dp[i%2][j], dp[i%2^1][j]].max
    s = 0
    l[i].size.times do |m|
      break if j + m + 1 > k
      s += l[i][m]
      dp[i%2][j+m+1] = [dp[i%2][j+m+1], dp[i%2^1][j] + s + m*(m+1)].max
    end
  end
end
p dp[1][k]