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

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

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

N.times do |i|
  v, w = items[i]

  (1..W).each do |j|
    dp[i + 1][j] = [dp[i + 1][j], dp[i][j - w] + v].max if j - w >= 0
    dp[i + 1][j] = [dp[i + 1][j], dp[i][j]].max
  end
end

p dp[N][W]

