n,w = gets.chomp.split.map(&:to_i)
wv_arr = n.times.map{gets.chomp.split(" ").map(&:to_i)}

dp = []

(0..n-1).each do |i|
  dp[i] ||= []
  dp[i+1] ||= []
  part_w, part_v = wv_arr[i]
  (0..w).each do |sum_w|
    a = dp[i][sum_w - part_w].to_i + part_v
    b = dp[i][sum_w].to_i
    if sum_w - part_w >= 0 && a > b
      dp[i+1][sum_w] = a
    else
      dp[i+1][sum_w] = b
    end
  end
end

puts dp[n][w]