import Data.List
import Data.Maybe (fromJust)
import qualified Data.ByteString.Lazy.Char8 as B
import Data.Bits
import Data.Array  --変数衝突
import Data.Array.Unboxed
import Data.Array.MArray
import Data.Array.ST
import Control.Monad
import Control.Monad.ST
import Debug.Trace

type Elem = Int
type SegT s = STUArray s Int Elem

{-
セグ木について
sup2によりnを２の冪にする
配列をdp[1]~[n] 変数はi'
セグ木をsegT[1]~[2*n-1] 変数はi
添え字iに対して、親ノードはi`div`2、子ノードは2*i,2*i+1
高さは (floor logBase 2 (fromIntegral i))+1
それぞれPは一点、Rは範囲の操作
-}
-- n+n/2+n/4+...<=2*n-1だが、子ノードの定義の仕方により2*n-1を超えることがある。

--nを超える最小の２の冪
sup2 :: Int -> Int
sup2 n = 2^(ceiling $ logBase 2 (fromIntegral n :: Double) :: Int)

newSegT :: MArray a e m => Int -> e -> m (a Int e)
newSegT n e = newArray (1,2*n-1) e

--logN
readPSegT :: SegT s -> Int -> Int -> Elem -> ST s Elem
readPSegT segT n i max0 = readPSegT' segT (n+i-1) max0
readPSegT' :: SegT s -> Int -> Elem -> ST s Int
readPSegT' segT i max0
  | 1 > i = return max0
  | otherwise = do
    a <- readArray segT i
    readPSegT' segT (i`div`2) (max a max0)

readRSegT :: SegT s -> (Int,Int) -> (Int,Int) -> Int -> ST s Elem
readRSegT segT (left,right) (l,r) i
  | r < left || right < l = return 0
--  | 2*n-1 < i   = error $ "modifyRSegT Error : i = " ++ (show i) ++ " " ++ (show ((left,right), (l,r))) ---Error??
  | left <= l && r <= right = do
    a' <- readArray segT i
    return a'
  | otherwise  = do
    let mid = (l+r)`div`2
    high <- readRSegT segT (left,right) (mid+1,r) (2*i+1)
    low  <- readRSegT segT (left,right) (l,mid) (2*i)
    return $ max high low

modifyPSegT :: SegT s -> Int -> Int -> (Elem -> Elem) -> ST s ()
modifyPSegT segT n i f = modifyPSegT' segT (n+i-1) f
modifyPSegT' :: SegT s -> Int -> (Elem -> Elem) -> ST s ()
modifyPSegT' segT i f
  | 1 > i = return ()
  | otherwise = do
    a <- readArray segT i
    writeArray segT i (f a)
    modifyPSegT' segT (i`div`2) f

--セグ木の更新,O(2*(logN))
--(left,right)の範囲で更新
modifyRSegT :: SegT s -> (Int,Int) -> (Int,Int) -> (Elem -> Elem) -> Int -> Int -> ST s ()
modifyRSegT segT (left,right) (l,r) f n i
  | r < left || right < l = return ()
--  | 2*n-1 < i   = error $ "modifyRSegT Error : i = " ++ (show i) ++ " " ++ (show ((left,right), (l,r))) ---Error??
  | left <= l && r <= right = do
   a' <- readArray segT i
   writeArray segT i (f a')
  | otherwise  = do
   let mid = (l+r)`div`2
   modifyRSegT segT (left,right) (mid+1,r) f n (2*i+1)
   modifyRSegT segT (left,right) (l,mid) f n (2*i)

dp_i :: SegT s -> Int -> [Int] -> [Int] -> ST s ()
dp_i segT n [] [] = return ()
dp_i segT n (h:hs) (a:as) = do
  maxa <- readRSegT segT (1,h-1) (1,n) 1
  modifyPSegT segT n h (max $ maxa+a)
  dp_i segT n hs as

solve :: Int -> [Int] -> [Int] -> Elem
solve n hs as = runST $ do
  segT <- newSegT n 0
  dp_i segT n hs as
  --readPSegT segT n n 0
  readArray segT 1

readBInt :: B.ByteString -> Int
readBInt = fst . fromJust . B.readInt

tmain :: B.ByteString -> Int
tmain cont =
   let remLines0 = map B.words (B.lines cont)
       [n']:remLines1 = remLines0
       n = readBInt n'
       line2:remLines2 = remLines1
       hs = map readBInt line2
       line3:remLines3 = remLines2
       as = map readBInt line3
   in solve (sup2 n) hs as

main :: IO ()
main = print . tmain =<< B.getContents


Measured memory_bytes: 12156