N, W = gets.split(' ').map(&:to_i)

vi = Array.new(101)
wi = Array.new(101)

dp = Array.new(101).map{Array.new(10010)}


N.times do |i|
	vi[i], wi[i] = gets.split(' ').map(&:to_i)
end

(W+1).times do |i|
	dp[0][i] = 0
end



for i in 0...N
	for w in 0..W
		if w >= wi[i]
			dp[i+1][w] = [dp[i][w-wi[i]]+vi[i], dp[i][w]].max
		else
			dp[i+1][w] = dp[i][w]
		end
	end
end


#for i in 0..N
#	for w in 0..W
#		print(dp[i][w].to_s+" ")
#	end
#	print("\n")
#end

print(dp[N][W].to_s+"\n")
