class Item
  attr_accessor :v, :w

  def initialize(v, w)
    @v, @w = v, w
  end
end

n, w = gets.split.map &:to_i
items = [Item.new(0, 0)]
n.times do
  value, weight = gets.split.map &:to_i
  items << Item.new(value, weight)
end

c = Array.new(n+1).map { Array.new(w+1, 0) }

(1..n).each do |i|
  (1..w).each do |j|
    tmp = j >= items[i].w ? c[i-1][j-items[i].w] + items[i].v : 0
    c[i][j] = [ tmp, c[i-1][j] ].max
  end
end

puts c[n][w]