def knapsack(items, budget)
    table = (0..1).map{ Array.new(budget+1, 0) }
    for i in 0..items.size-1
        c, v = items[i]
        for j in 0..budget
            x = table[0][j]
            y = (j >= c ? table[0][j-c] + v : 0)
            table[1][j] = x > y ? x : y
        end
        table << table.shift
    end
    table[0][budget]
end

n, budget = gets.split.map &:to_i
items = $<.map{|s| s.split.map(&:to_i).reverse}
p knapsack(items, budget)