import Data.List
import Data.Array
import Control.Applicative
{-ナップザックDP-}
type Pair = (Int,Int)

main = do
    [n,wmax] <- map read . words <$> getLine
    weights <- sequence $ replicate n ((\[x,y] -> (x,y)) . map read . words <$> getLine)
    print $ solve wmax weights

solve :: Int -> [Pair] -> Int
solve wmax weights = (g wmax weights) !! wmax

g ::  Int -> [Pair] -> [Int]
g wmax = foldl (addPair wmax) dp0 
    where dp0 = replicate (wmax+1) 0

addPair :: Int -> [Int] -> Pair -> [Int]
addPair wmax dp (v,w) = [ f index dp (v,w) | index <- [0..wmax] ]

f :: Int -> [Int] -> Pair -> Int
f index dp (v,w) = max before after
    where before = dp !! index
          after = if w' >= 0 then (dp !! w') + v else -1
          w' = index - w



