{-# OPTIONS_GHC -O2 #-}
import Control.Applicative
import qualified Data.Vector.Unboxed as V

main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  print $ V.maximum (resolve capa (V.enumFromStepN 0 0 (capa+1)) goods)

resolve capa capaV ([v,w,m]:xs)
  | null xs   = koushin' m 1 capaV
  | otherwise = resolve capa (koushin' m 1 capaV) xs
  where
    koushin' m x capaV
      | m == 0 || w > capa  = capaV
      | (w*x) > capa        = koushin' m (x-1) capaV
      | x >= m              = koushin capaV [v*m,w*m] (capa-(w*m)) []
      | otherwise = koushin' (m-x) (x*2) (koushin capaV [v*x,w*x] (capa-(w*x)) [])
    koushin capaV [v,w] n koushinList
      | n == 0 && capaV V.! w <= v      = capaV V.// ((w,v):koushinList)
      | n == 0                          = capaV V.// koushinList
      | oldValue == 0                   = next
      | capaV V.! (n+w) >= v + oldValue = next
      | otherwise = koushin capaV [v,w] (n-1) ((n + w, v + oldValue):koushinList)
      where
        oldValue = capaV V.! n
        next     = koushin capaV [v,w] (n-1) koushinList