N, Q = gets().split.map(&:to_i)
w = Array.new( N, 0 )
v = Array.new( N, 0 )

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

dp = Array.new(N+1){ Array.new(Q+1, 0) }

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

puts dp[N][Q]