{-# OPTIONS_GHC -O2 #-}
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'
  | otherwise = resolve capa koushin' xs
  where
    koushin' =  koushin capaMap [v,w,m] 0
    koushin capaMap [v,w,m] n
      | m == 0                                = capaMap
      | (n == (capa-w) && oldValue /= 0) && newValue < oldValue + v =  Map.insert (n+w) (v+oldValue) capaMap
      | n ==  (capa-w)                           = capaMap
      | n == 0 && newValue <= v   = next'
      | oldValue == 0                         = next
      | capaMap Map.! (n+w) >= v + oldValue   = next
      | otherwise = next'
      where
        oldValue = capaMap Map.! n
        newValue =capaMap Map.! (n+w)
        next     = koushin capaMap [v,w,m-1] (n+1)
        next'    = koushin (Map.insert (n+w) (v + oldValue) capaMap) [v,w,m-1] (n+1)