CF1483C.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.

爱丽丝正在游览纽约市。为了使这次旅行更加有趣，爱丽丝将拍摄城市天际线的照片，并将这一组照片作为礼物送给鲍勃。然而，她希望找到一组具有最大“美感”的照片，因此需要你的帮助。

城市中有 $n$ 座建筑，第 $i$ 座建筑的高度为正整数 $h_i$。这 $n$ 座建筑的高度互不相同。此外，每座建筑还有一个美感值 $b_i$。注意，美感值可正可负，因为城市中也存在一些丑陋的建筑。

一组照片由一张或多张天际线照片组成。每张照片包含天际线中一个或多个建筑，且这些建筑的编号构成一段连续的区间。每座建筑必须恰好出现在一张照片中。这意味着：如果某座建筑未出现在任何照片中，或者某座建筑出现在多张照片中，则该组照片是无效的。

一张照片的美感值等于其中最矮建筑的美感值 $b_i$。一组照片的总美感值等于其中所有照片的美感值之和。请帮助爱丽丝找出所有合法照片组所能达到的最大总美感值。

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$.

第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$），表示天际线上建筑物的数量。

第二行包含 $n$ 个互不相同的整数 $h_1, h_2, \ldots, h_n$（$1 \le h_i \le n$）。其中第 $i$ 个数表示第 $i$ 座建筑物的高度。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$-10^9 \le b_i \le 10^9$）。其中第 $i$ 个数表示第 $i$ 座建筑物的美观度。

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

输出一个数字，表示爱丽丝为天际线的一组有效照片所能达到的最大美观度。

In the first example, Alice can achieve maximum beauty by taking five photos, each one containing one building.

In the second example, Alice can achieve a maximum beauty of $10$ by taking four pictures: three just containing one building, on buildings $1$, $2$ and $5$, each photo with beauty $-3$, $4$ and $7$ respectively, and another photo containing building $3$ and $4$, with beauty $2$.

In the third example, Alice will just take one picture of the whole city.

In the fourth example, Alice can take the following pictures to achieve maximum beauty: photos with just one building on buildings $1$, $2$, $8$, $9$, and $10$, and a single photo of buildings $3$, $4$, $5$, $6$, and $7$.

在第一个例子中，Alice 通过拍摄五张照片（每张照片恰好包含一座建筑）来达到最大美观度。

在第二个例子中，Alice 可以通过拍摄四张照片来达到最大美观度 $10$：其中三张照片各只包含一座建筑，分别对应建筑 $1$、$2$ 和 $5$，其美观度分别为 $-3$、$4$ 和 $7$；另一张照片包含建筑 $3$ 和 $4$，其美观度为 $2$。

在第三个例子中，Alice 将仅拍摄一张涵盖整座城市的全景照片。

在第四个例子中，Alice 可以通过以下方式拍摄照片以达到最大美观度：分别对建筑 $1$、$2$、$8$、$9$ 和 $10$ 各拍摄一张仅含该建筑的照片，并另拍一张包含建筑 $3$、$4$、$5$、$6$ 和 $7$ 的照片。