require 'pp'

N,W = readline.split.map(&:to_i)
A = [nil] + N.times.each.map {|i| readline.split.map(&:to_i) }

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

(1..N).each do |i|
  (1..W).each do |w|
    wi,vi = A[i]
    a = dp[i-1][w]
    if wi <= w and (b = dp[i-1][w-wi] + vi) > a
      dp[i][w] = b
    else
      dp[i][w] = a
    end
  end
end

puts dp.last.last


