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 DP s = STArray s Int ([Int],Int)

items = fst.snd
value = snd.snd
weight = fst

mkArray :: DP s -> [(Int,([Int],Int))] -> ST s Int
mkArray _ [] = return 100000
mkArray dparr ((w,x):xs) = do
   writeArray dparr w x
   mkArray dparr xs >>= return.min w

dp_i :: DP s -> Int -> Int -> Int -> ST s Int
dp_i dparr minw maxw i = do
  ls <- forM [minw..(i-minw)] $ \j -> do
      let elems [] ls = False
          elems (x:xs) ls = if elem x ls then True else elems xs ls
      (is0,v0) <- readArray dparr i
      (is1,v1) <- readArray dparr j
      (is2,v2) <- readArray dparr (i-j)
      if v0 >= v1+v2 || elems is1 is2  then return ()
             else writeArray dparr i $ traceShowId (is1++is2,v1+v2)
      if minw+i > maxw then return $ max v0 (v1+v2) else return 0
  return $ maximum ls

solve :: [(Int,([Int],Int))] -> Int -> ST s Int
solve ls maxw = do
  dparr <- newArray (1,maxw) ([],0)
  minw <- mkArray dparr ls
  dparr' <- mapIndices (minw,maxw) id dparr
  forM_ [minw..maxw-minw] $ dp_i dparr' minw maxw --dp
  ans <- maximum <$> forM [maxw-minw+1..maxw] (dp_i dparr' minw maxw) --dp
  return ans


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