def knapsack(items, budget)
	table = (0..1).map{ Array.new(budget+1, 0) }
	for i in 0..items.size-1
		c, v = items[i]
		for j in 0..budget
			x = table[0][j]
			y = (j >= c ? table[0][j-c] + v : 0)
			table[1][j] = x > y ? x : y
		end
		table << table.shift
	end
	table[0].max
end

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

hash = {}

n.times { 
	price, kind = gets.split.map(&:to_i)
	hash[kind] ||= []
	hash[kind] << price
}

hash.each{|kind, prices|
	i = 0
	hash[kind] = prices	
		.sort
		.reverse
		.inject([0]){|a, p|
			i += 1
			a + [a[-1] + p + 2 * i - 2]
		}
}

a = hash.values

table = (0..1).map{ Array.new(k+1, 0) }
for i in 0..a.size-1
	for j in 0..k
		table[1][j] = 
			(0..[a[i].size-1, j].min)
			.map{|l| table[0][j-l] + a[i][l]}
			.max
	end
	p table[1]
	table << table.shift
end
p table[0][k]