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

-- Knapsack DP
-- 1<=maxw<=10^9
-- 1<= v  <=10^3
-- 1<= n  <=100
type Item  = (Int,Int)
type Items = [Item]
type DP s = STUArray s (Int,Int) Int

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

solve :: [(Int,Item)] -> Int -> Int -> Int -> ST s Int
solve ls n maxw maxv = do
  dparr <- newArray ((1,0),(n,maxv)) (maxw+1)
  forM_ ls $ \(i,item) -> dp_i dparr item maxw maxv i --dp
  let find :: DP s -> Int -> ST s Int
      find dparr' j = do
        w0 <- readArray dparr' (n,j)
        if w0 > maxw then find dparr' (j-1) else return j
  ans <- find dparr maxv
  return ans

main :: IO ()
main = do
  [n,maxw] <- map read.words <$> getLine
  let forM' [] = return (0,[])
      forM' (n:ns) =  do
      (w:v:emp) <- map read.words <$> getLine :: IO [Int]
      (v1,ls) <- forM' ns
      return (v+v1,(n,(w,v)):ls)
  (maxv,ls) <- forM' [1..n]
  putStrLn $ show $ runST $ solve ls n maxw maxv
