def solve_knapsack(w, v, q)

	n = w.length
	inf = 1e9.to_i
	ans = [-inf] * (q + 1)

	ans[0] = 0

	(w.zip(v)).each do |wi, vi|
		(0..(q-wi)).each do |kkk|
			k = (q-wi) - kkk
			ans[k+wi] = [ans[k+wi], ans[k] + vi].max
		end
	end

	ans.max
	
end


if __FILE__ == $0

	n, q = gets().split().map(&:to_i)
	v, w = [], []
	n.times do |i|
		vi, wi = gets().split().map(&:to_i)
		v << vi
		w << wi
	end

	a = solve_knapsack(w, v, q)
	puts a

	#w = [3,2,4,1,3]
	#v = [2,3,3,2,6]
	#q = 10
	#a = solve_knapsack(w, v, q)
	#puts "ans: #{a}"

end