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

type DP = Array Int Int

g :: Int -> [Pair] -> DP
g wmax = foldl addPair dp0 
    where dp0 = array (0,wmax) (zip [0..wmax] (repeat 0))

addPair :: DP -> Pair -> DP
addPair before pair = array (0,leng-1) $ zip [0..leng-1] [ addPi index before pair | index <- [0..leng-1] ]
    where leng = length before
           

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

