N, W = gets.split.map(&:to_i)
value = []
weight = []
N.times do |i|
  value[i], weight[i] = gets.split.map(&:to_i)
end
dp = Array.new(N+1){Array.new(W+1, 0)}
(0...N).each do |i|
  (0..W).each do |j|
    if j < weight[i]
      dp[i+1][j] = dp[i][j]
    else
      dp[i+1][j] = [dp[i][j - weight[i]] + value[i], dp[i][j]].max
    end
  end
end
p dp[N][W]
