n, w_max = gets.split.map(&:to_i)
w = []
v = []
$<.map{|l|
  wi, vi = l.split.map(&:to_i)
  w << wi
  v << vi
}
dp = []
2.times{ dp << Array.new(w_max+1, 0) }
i0 = 1
i1 = 0
n.times{|i|
  i0,i1 = i1,i0
  (w_max+1).times{|j|
    dp[i1][j] = j>=w[i] ? [ dp[i0][j] , dp[i0][j-w[i]]+v[i] ].max : dp[i0][j]
  }
}
p dp[i1][w_max]
