N, W = gets.split.map(&:to_i)
v = []
w = []

N.times do |i|
	v[i], w[i] = gets.split.map(&:to_i)
end

dp = Array.new(N+2).map{Array.new(W+2, 0)}

N.times do |i|
	(W+1).times do |j|
		if j >= w[i]
			dp[i+1][j] = [dp[i][j-w[i]] + v[i], dp[i][j]].max
		else
			dp[i+1][j] = dp[i][j]
		end
	end
end
 
puts dp[N][W]
