N, W = gets.chomp.split(' ').map(&:to_i)
@value = []
@weight = []
N.times do |i|
  @value[i], @weight[i] = gets.chomp.split(' ').map(&:to_i)
end

dp = Array.new(N){[0, 0]}

def knapsack(i, w)
  return 0 if i == 0
  [
    knapsack(i - 1, w),
    knapsack(i - 1, w - @weight[i]) + @value[i]
  ].max
end

puts knapsack(N - 1, W)
