{-# OPTIONS_GHC -Wall #-}

import Control.Monad
import Data.Array

readInt :: String -> Int
readInt = read

calcDp :: Int -> Int -> Array Int Int -> Array Int Int -> Array (Int,Int) Int
calcDp n wmax vs ws = dp
    where
        -- i種類目までで容量jで実現できる最大価値
        dp = listArray ((0,0),(n,wmax)) [f i j | i<-[0..n], j<-[0..wmax]]
        f _ 0 = 0
        f 0 _ = 0
        f i j
            | j >= w    = max (v+dp!(i,j-w)) (dp!(i-1,j))
            | otherwise = dp!(i-1,j)
            where
                v = vs!(i-1)
                w = ws!(i-1)

main :: IO ()
main = do
    [n,wmax] <- fmap (map readInt . words) getLine
    vws      <- replicateM n $ do
        [v,w] <- fmap (map readInt . words) getLine
        return (v,w)
    let vs = listArray (0,n-1) $ map fst vws
    let ws = listArray (0,n-1) $ map snd vws

    let dp  = calcDp n wmax vs ws
    let ans = dp!(n,wmax)

    --print $ dp
    print $ ans

