import Data.Array
import qualified Data.ByteString.Char8 as C
import Data.List

main = C.interact $ put . sol . get

get = fmap (unfoldr (C.readInt . C.dropWhile (==' '))) . C.lines

put = C.pack . show

sol ([n,m]:wvs) = a!(n, m)
  where
  w = listArray (1,n) $ head <$> wvs
  v = listArray (1,n) $ last <$> wvs
  a = array ((0,0),(n,m)) $
    [((0,j), 0) | j <- [0..m]] ++
    [((i,0), 0) | i <- [1..n]] ++
    [((i,j), b) | i <- [1..n], j <- [1..m], let b = f i j]
  f i j
    | w!i>j     = a!(i-1,j)
    | otherwise = max (a!(i-1,j)) (a!(i-1,j-w!i) + v!i)