A14149 | Skyline Photo

Alice is visiting New York City. To make the trip fun, Alice will take photos of the city skyline and give the set of photos as a present to Bob. However, she wants to find the set of photos with maximum beauty and she needs your help.

There are $n$ buildings in the city, the $i$ -th of them has positive height $h_i$ . All $n$ building heights in the city are different. In addition, each building has a beauty value $b_i$ . Note that beauty can be positive or negative, as there are ugly buildings in the city too.

A set of photos consists of one or more photos of the buildings in the skyline. Each photo includes one or more buildings in the skyline that form a contiguous segment of indices. Each building needs to be in exactly one photo. This means that if a building does not appear in any photo, or if a building appears in more than one photo, the set of pictures is not valid.

The beauty of a photo is equivalent to the beauty $b_i$ of the shortest building in it. The total beauty of a set of photos is the sum of the beauty of all photos in it. Help Alice to find the maximum beauty a valid set of photos can have.

The first line contains an integer $n$ ( $1 \le n \le 3 \cdot 10^5$ ), the number of buildings on the skyline.

The second line contains $n$ distinct integers $h_1, h_2, \ldots, h_n$ ( $1 \le h_i \le n$ ). The $i$ -th number represents the height of building $i$ .

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ( $-10^9 \le b_i \le 10^9$ ). The $i$ -th number represents the beauty of building $i$ .

Print one number representing the maximum beauty Alice can achieve for a valid set of photos of the skyline.