n, limit = gets.chomp.split.map(&:to_i)
sack = Array.new(limit + 1, 0)
n.times{
    v, w = gets.chomp.split.map(&:to_i)
    prev = sack.dup
    1.upto(limit){|j|
        sack[j] = [(j < w) ? 0 : prev[j - w] + v, prev[j]].max
    }
}
p sack.last