n, w = gets.chomp.split(' ').map(&:to_i)

$box = []

n.times do
  $box << gets.chomp.split(' ').map(&:to_i)
end

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

def max(a, b)
  a < b ? b : a
end

n.times do |i|
  (w + 1).times do |j|
    if j == 0
      table[i][j] = 0
      next
    end
    table[i][j] = if j < $box[i][1]
                    table[i - 1][j]
                  else
                    max(table[i - 1][j - $box[i][1]] + $box[i][0], table[i - 1][j])
                  end
  end
end

puts table[n - 1][w]

