{-# OPTIONS_GHC -O2 #-}
import Control.Applicative
import qualified Data.HashMap.Strict as Map
 
main = do
    [_,capa] <- map (read :: String -> Int) . words <$> getLine
    goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
--    print $ maximum $ map snd $ Map.toList (resolve capa (Map.fromList (zip [0..capa] [0,0..])) goods)
    print $ Map.toList (resolve capa (Map.fromList (zip [0..capa] [0,0..])) goods)

resolve capa capaMap ([v,w]:xs)
  | xs == []  = koushin'
  | otherwise = resolve capa koushin' xs
  where
    koushin' 
      | w > capa  = capaMap
      | otherwise = koushin capaMap [v,w] w
    koushin capaMap [v,w] n
      | n > capa                            = capaMap
      | capaMap Map.! n >= v + oldValue     = next
      | (n-w) == 0 && capaMap Map.! w <= v  = next'
      | oldValue == 0                       = next
      | otherwise                           = next'
      where
        oldValue = capaMap Map.! (n - w)
        next     = koushin capaMap [v,w] (n+1)
        next'    = koushin (Map.insert n (v + oldValue) capaMap) [v,w] (n+1)