n, W = gets.rstrip.split.map(&:to_i)
xs = n.times.map{ gets.rstrip.split.map(&:to_i) }
ws, vs = [], []
xs.each{|x| ws << x[0]; vs << x[1]}

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

(0..n-1).each do | i |
  (0..W).each do | w |
    if ws[i] <= w
      # dp[i][w-ws[i]] は dp をテーブルとして見たときのジャンプ元を示している
      # ジャンプ先はdp[i+1][w]
      #   i-1 -> i
      #   [w-ws[i]] -> w
      dp[i+1][w] = [dp[i][w-ws[i]]+vs[i], dp[i][w]].max
    else
      dp[i+1][w] = dp[i][w]
    end
  end
end
#dp.each do | d |
#  p d
#end
p dp[-1].max