# frozen_string_literal: true

def chmax(a, b)
  a > b ? a : b
  end
n, w = gets.split.map(&:to_i)
weight = []
value = []
n.times do
  a, b = gets.split.map(&:to_i)
  weight << a
  value << b
end
dp = Array.new(110).map { Array.new(100_010, 0) }

(0..n - 1).each do |i|
  (0..w).each do |j|
    dp[i + 1][j] = dp[i][j]
    if j - weight[i] >= 0
      dp[i + 1][j] = chmax(dp[i + 1][j], dp[i][j - weight[i]] + value[i])
    end
  end
end

puts dp[n][w]
