n, w = gets.split.map &:to_i
wi, vi = n.times.map{ gets.split.map &:to_i }.transpose

dp = Array.new(n).map{Array.new(w+1).map{-1}}
dp[0][0] = 0
dp[0][wi[0]] = vi[0]

1.upto(n-1).each{|i|
    0.upto(w).each{|j|
        if dp[i-1][j] != -1
            if dp[i][j] < dp[i-1][j]
                dp[i][j] = dp[i-1][j]
            end

            if j + wi[i] <= w && dp[i][j+wi[i]] < dp[i-1][j] + vi[i]
                dp[i][j+wi[i]] = dp[i-1][j] + vi[i]
            end
        end
    }
}

puts dp.last.max
