import Control.Applicative
import qualified Data.IntMap.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)

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