import Data.List
--import Data.Array
import Data.Array.Unboxed
import Data.Array.MArray
import Data.Array.ST
--import Data.Vector as V
import Control.Monad
import Control.Monad.ST
import Debug.Trace

type Item  = (Int,Int)
type Items = [Item]
type DP s = STUArray s (Int,Int) Int

dp_i :: DP s -> Item -> Int -> Int -> ST s ()
dp_i dparr (w,v) maxw 1 = forM_ [w..maxw] $ \j -> writeArray dparr (1,j) v
dp_i dparr (w,v) maxw i = do
  forM_ [1..w] $ \j -> readArray dparr (i-1,j) >>= writeArray dparr (i,j)
  forM_ [w..maxw] $ \j -> do
    v0 <- readArray dparr (i-1,j)
    v1 <- readArray dparr (i-1,j-w)
    if v0 >= v1+v then writeArray dparr (i,j) v0
        else writeArray dparr (i,j) (v1+v)

solve :: [(Int,Item)] -> Int -> Int -> ST s Int
solve ls n maxw = do
  dparr <- newArray ((1,0),(n,maxw)) 0
  forM_ ls $ \(i,item) -> (dp_i dparr item maxw i) --dp
  ans <- readArray dparr (n,maxw)
  return ans

main :: IO ()
main = do
  [n,maxw] <- map read.words <$> getLine
  ls <- forM [1..n] $ \i -> do
      (w:v:emp) <- map read.words <$> getLine :: IO [Int]
      return (i,(w,v))
  putStrLn $ show $ runST $ solve ls n maxw
