N, W = gets.split.map(&:to_i)
ws = [0]
vs = [0]

N.times do
  w, v = gets.split.map(&:to_i)
  ws << w
  vs << v
end

dp = [0] * (W + 1)

1.upto(N) do |i|
  dp = dp.map.with_index do |v_old, w_max|
    w = w_max - ws[i]
    if 0 <= w
      [dp[w_max], dp[w] + vs[i]].max
    else
      v_old
    end
  end
end

puts dp.last
