n, w = gets.chomp.split(" ").map(&:to_i)
dp = Array.new(n + 1).map{Array.new(w + 1, 0)}
(1..n).each do |i|
	vv, ww = gets.chomp.split(" ").map(&:to_i)
	ww.times do |j|
		dp[i][j] = dp[i - 1][j]
	end
	(ww..w).each do |j|
		dp[i][j] = [dp[i - 1][j], dp[i - 1][j - ww] + vv].max
	end
end
puts dp[n][w]






