n, knapsack = gets.split.map(&:to_i)
goods = n.times.map {gets.split.map(&:to_i)}

dp = Array.new(n + 1) {Array.new(10001, 0)}

goods.each_with_index do |(value, weight), i|
  (0..knapsack).each do |w|
    dp[i + 1][w] = if w >= weight
      [dp[i][w - weight] + value, dp[i][w]].max
    else
      dp[i][w]
    end
  end
end

puts dp[n][knapsack]
