import Control.Applicative
import Control.Monad

{- Nil ??? 1 ??????Cons Int x ??? Int ?? X ?????¨???????????????-}
data F x = Nil | Cons Int x
{- F?????¢????????????????????????????????????????????£?¨? -}
instance Functor F where
  fmap f Nil = Nil
  fmap f (Cons x xs) = Cons x (f xs)

newtype FixF f = InF { outF :: f (FixF f) }

type IntList = FixF F

{- IntList ????§???????????£??????¢??° -}
nil :: IntList
nil = InF Nil
cons :: Int -> IntList -> IntList
cons a as = InF $ Cons a as

cata :: Functor f => (f a -> a) -> FixF f -> a
cata phi = phi . fmap (cata phi) . outF

ana :: Functor f => (a -> f a) -> a -> FixF f
ana psi = InF . fmap (ana psi) . psi

hylo :: Functor f => (f x -> x) -> (y -> f y) -> (y -> x)
hylo phi psi = cata phi . ana psi

dyna :: Functor f => (f (Cofree f x) -> x) -> (y -> f y) -> (y -> x)
dyna phi psi = extract . hylo ap psi where
  ap a = Cf $ InF $ FCons (phi a) (fmap unCf a)

data Fx f a x = FCons a (f x)
instance Functor f => Functor (Fx f a) where
  fmap f (FCons x xs) = FCons x (fmap f xs)

newtype Cofree f a = Cf { unCf :: FixF (Fx f a) }

instance Functor f => Functor (Cofree f) where
  fmap f = Cf . ana (phi . outF) . unCf where
    phi (FCons a b) = FCons (f a) b

extract :: Functor f => Cofree f a -> a
extract cf = case (outF $ unCf cf) of
  FCons a _ -> a

sub :: Functor f => Cofree f a -> f (Cofree f a)
sub cf = case (outF $ unCf cf) of
  FCons _ b -> fmap Cf b

data KSTree a = KSTree (Int, Int) (Maybe a)
instance Functor KSTree where
  fmap f (KSTree a Nothing)  = KSTree a Nothing
  fmap f (KSTree a (Just b)) = KSTree a (Just (f b))

knapsack c v w = dyna phi psi $ (n,c) where
  n = length w
  psi (0,0) = KSTree (n,0) Nothing
  psi (0,j) = KSTree (n,j) (Just (n, j - 1))
  psi (i,j) = KSTree (n - i,j) (Just (i - 1, j))

  phi (KSTree _ Nothing) = 0
  phi (KSTree (i,j) (Just cs))
    | i == n      = 0
    | w !! i <= j = max x1 x2
    | otherwise   = x1
    where
      x1 = extract cs
      x2 = (v !! i) + (back 0 (w !! i) cs)

  back 0 0 cs = extract cs
  back i 0 cs = case sub cs of
    (KSTree _ (Just b)) -> back (i - 1) 0 b
  back i j cs = back (i + j * (n + 1)) 0 cs

decmp :: [Int] -> (Int,Int)
decmp [a,b] = (a,b)

main = do
  [n, w] <- (map read . words) <$> getLine
  elems <- unzip . map (decmp . map read . words) <$> replicateM n getLine
  print $ uncurry (knapsack w) elems