import Control.Monad
import Data.Array.IO
import Data.Array.IArray

main = do
    [n,w] <- map read.words<$>getLine
    dataset <- replicateM n $ (\[x,y] -> (x,y)).map read.words<$>getLine
    let (vlist,wlist) = unzip dataset
        maxi = length vlist
        vs = array (1,maxi) $ zip [1..] vlist :: Array Int Int
        ws = array (1,maxi) $ zip [1..] wlist :: Array Int Int

    ksarr <- newArray ((0,0),(maxi,w)) 0      :: IO (IOArray (Int, Int) Int)
    forM_ [1..maxi] $ \i -> do
        forM_ [1..w] $ \j -> do
            knapsack i j vs ws ksarr
    print =<< readArray ksarr (maxi,w)

knapsack :: Int -> Int -> Array Int Int -> Array Int Int -> IOArray (Int, Int) Int -> IO ()
knapsack i j vs ws ksarr = do
    let lpos = j-ws!i
    l <- if lpos < 0 then return 0
                     else readArray ksarr (i-1,lpos)
    t <- readArray ksarr (i-1,j)
    let m = if lpos < 0 then 0
                        else max (l + vs!i) t
    writeArray ksarr (i,j) m