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

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

accum = []
hash.each{|kind, prices|
	accum << [0]
	prices.sort.reverse.each_with_index{|p, i|
		a = accum[-1]
		a << a[-1] + p + 2 * i
	}
}

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