n, w = gets.chomp.split.map(&:to_i)
items = []
n.times{items << gets.chomp.split.map(&:to_i)}

maxes = Array.new(w + 1, 0)
items.each{|v, w| maxes[w] = v if maxes[w] < v}
#p maxes
#puts
1.upto(w){|i|
    max = 0
    1.upto(i / 2){|j|
        val = maxes[j] + maxes[i - j]
        max = val if max < val
    }
    maxes[i] = [max, maxes[i]].max
#p maxes
}
puts maxes.last