import Data.Array.Unboxed


--価値と重さアレイ、使用する要素の最大インデックス、重さ制限、ナイーブ再帰。それぞれについて入れるかどうか。
naive_rec::Array Int (Int,Int)-> Int -> Int -> Int
naive_rec item 0 limit = 0
naive_rec item i limit = let no_i_v = naive_rec item (i-1) limit in
                         let usable_i = if ( limit - (snd (item!i)) )>=0
                                          then let use_v = naive_rec item (i-1) (limit - (snd (item!i))) in
                                               use_v+ (fst (item!i))
                                          else no_i_v in
                         max usable_i no_i_v

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 no_i = prev!k in
                              let usable_i = if (k - (snd (item!i))) >=0
                                                then let use_i = (prev!(k-(snd (item!i)))) in
                                                     use_i + (fst (item!i))
                                                else no_i in
                              max no_i usable_i
                            | k <- [0..limit]]
                        | (prev,i) <- zip (memo_ls item m limit) [1..m]]

--vwリスト、リスト要素数、重さ制限、答え。
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)
