n,w = gets.chomp.split.map(&:to_i)

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

1.upto(n) do |i|
  www,v = gets.chomp.split.map(&:to_i)

  1.upto(w) do |ww|
    if ww-www < 0
      dp[i][ww] = dp[i-1][ww]
    else
      dp[i][ww] = [dp[i-1][ww], dp[i-1][ww-www] + v].max
    end
  end
end

p dp[n][w]
