N, W = gets.split.map &:to_i
dp = Array.new(W + 1){0}
w , v = [],[]
N.times do |i|
  w[i], v[i] = gets.split.map &:to_i
end

0.upto(N - 1) do |i|
  W.downto(w[i]) do |j|
    temp = dp[j - w[i]] + v[i]
    dp[j] = temp if dp[j] < temp
  end
end
p dp[-1]