import Control.Monad
import Data.Array
main = do
  [n,m] <- map read . words <$> getLine
  wvs <- replicateM n $ map read . words <$> getLine
  let a = listArray (0,n-1) wvs
      memo = listArray ((0,0),(n,m)) [f i j| i<-[0..n], j<-[0..m]]
      f i j
        | i == n = 0
        | w+j > m = memo!(i+1,j)
        | otherwise = (memo!(i+1,j)) `max` (v+memo!(i+1,j+w))
        where [w,v] = a!i
  print $ f 0 0