import Data.List (sort)
import qualified Data.IntMap as M
import Data.Maybe (fromJust)

main = interact $ show . solve . map (map read . words) . lines


solve ([n]:xs:ys:zs:_) = ans
    where
        n1 = n + 1
        zzs = sort zs
        es = foldl f M.empty $ zip [0..n] xs
        f m ix = foldl (g ix) m $ zip [0..n] ys
        g (i,x) m (j,y) | i + j > n = m
                | otherwise = M.insertWith (++) (i+j) [(x+y,i*n1+j,(i-1)*n1+j,i*n1+j-1)] m
        ans = fst . fromJust . M.lookup 0 $ M.foldr h M.empty es
        h vs m = foldl u m vs
        u m (r,k,k1,k2) = ret where
            ff aa@(a,_) bb@(b,_) = if a > b then aa else bb 
            ret = case M.findWithDefault (0, zzs) k m of
                (c, z:zs) | z <= r -> M.insertWith ff k2 (c+1,zs) $ M.insertWith ff k1 (c+1,zs) m
                _ -> m