import Data.Array((!), listArray)
main = interact $ show.helper.(map read).words
helper (n:wei:xs) = maximum $ rec ws vs
                  where (ws, vs) = cvr xs
                        rec [] [] = listArray (1, wei) $ replicate wei 0
                        rec (w:ww) (v:vv) = fff w v $ rec ww vv
                        fff w v dp = listArray (1, wei) $ 
                                   [max (f (i-w)) (dp!i)| i<-[1..wei]]
                              where f i
                                     | i == 0 = v
                                     | i < 0  = 0
                                     | otherwise = v + dp!i

cvr (a:b:[]) = ([a], [b])
cvr (a:b:ss) = (a:x, b:y)
               where (x, y) = cvr ss

