def gs() gets.chomp end
def gi() gets.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end
def ang(n) Array.new(n){gsmi} end
def debug(k,v) puts "#{k}: #{v}" end
def desc(ar) ar.sort!{|x,y|y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end
def arrays(n,num) #要素数、配列数
  ret = Array.new(num){Array.new(n)}
  n.times do |i|
    ins = gsmi
    num.times{|j| ret[j][i] = ins[j] }
  end
  ret
end

$stdin = File.open('input.txt') if File.exist?('input.txt')

n,w_max = gsmi #100, 10**5
w,v = arrays(n,2)
w.unshift 0
v.unshift 0

dp = Array.new(n+1){Array.new(w_max+1){0}}
(1..n).each do |i|
  (0..w_max).each do |j|
    if (j-w[i])>=0
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
    else
      dp[i][j] = dp[i-1][j]
    end
  end
end

puts dp[-1].max
