main :: IO ()
main = print . solve  =<< input

input :: IO (Int, [[Int]])
input = do
    [n, w] <- readInts
    carriages <- mapM (const readInts) [0..n-1]
    return (w, carriages)
    where
        readInts = flip fmap getLine $ map read . words

solve :: (Int, [[Int]]) -> Int
solve (maxW, cs) = solve' (replicate (maxW + 1) 0) cs
    where
        solve' dp [] = last dp
        solve' dp ([v, w]:cs) =
            let
                values :: [(Maybe Int, Int)]
                values = zip (replicate w Nothing ++ map Just dp) dp 
                dp' = flip map values $ \(prevSmallV, prevV) -> maybe prevV (max prevV . (v +)) prevSmallV
            in solve' dp' cs
