{-# OPTIONS_GHC -O2 #-}
import Data.Array.Unboxed

naive_rec::Array Int (Int,Int)->Int->Int->Int
naive_rec _    0 _     = 0
naive_rec item i limit = let (v_i,w_i) = item!i in
                          maximum [ (naive_rec item (i-1) (limit - w_i*k)) + (v_i*k) | k <- [0..div limit w_i] ]


memo_ls::Array Int (Int,Int)->Int->Int->[UArray Int Int]
memo_ls item m limit = (listArray (0,limit) (replicate (limit+1) 0)):
                       [ listArray (0,limit) [ let (v_i,w_i) = item!i in
                                               maximum [ (prev!(l - j*w_i)) + (j*v_i)
                                                       | j <- [0..div l w_i]]
                                             | l <- [0..limit] ]
                       | (prev,i) <- zip (memo_ls item m limit) [1..m]]


--vwlist,item_idx_bound,limit,Ans
solver::[(Int,Int)]->Int->Int->Int
solver item_ls m limit = let item = listArray (1,m) item_ls in
                         (last (memo_ls item m limit))!limit

n_tp_get::Int->IO [(Int,Int)]
n_tp_get 0 = return []
n_tp_get n = do
  vw<-getLine
  let v:w:[]= map read (words vw)
  rest<-n_tp_get (n-1)
  return ((v,w):rest)

main::IO()
main=do
  ml<-getLine
  let m:l:[]=map read (words ml)
  dat<-n_tp_get m
  print (solver dat m l)

