Alice 正在访问纽约市。为了让旅行变得有趣,爱丽丝将拍摄城市天际线的照片,并将这组照片作为礼物送给鲍勃。然而,她想要找到一组最美丽的照片,她需要你的帮助。
城市中有 $$$n$$$ 栋建筑物,其中第 $$$i$$$ 的高度为正 $$$h_i$$$。城市中所有$$$n$$$建筑物的高度都不同。此外,每栋建筑都有一个美丽值$$$b_i$$$。请注意,美可以是积极的,也可以是消极的,因为城市中也有丑陋的建筑。
一组照片由一张或多张天际线上建筑物的照片组成。每张照片都包含天际线上的一座或多座建筑物,这些建筑物形成了连续的索引段。每座建筑物都需要出现在一张照片中。这意味着,如果建筑物没有出现在任何照片中,或者建筑物出现在多张照片中,则该组图片无效。
照片的美感相当于照片中最矮的建筑物的美感 $$$b_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$$$ 的美丽。
输出
打印一个数字,代表爱丽丝对于一组有效的天际线照片所能达到的最大美感。
示例
输入 #1
5 1 2 3 5 4 1 5 3 2 4
输出 #1
15
输入 #2
5 1 4 3 2 5 -3 4 -10 2 7
输出 #2
10
输入 #3
2 2 1 -2 -3
输出 #3
-3
输入#4
10 4 7 3 2 5 1 9 10 6 8 -4 40 -46 -8 -16 4 -10 41 12 3
输出#4
96
注意
在第一个示例中,Alice 可以通过拍摄五张照片(每张照片包含一座建筑物)来实现最大的美感。
在第二个示例中,Alice 可以通过拍摄四张照片来实现 $$$10$$$ 的最大美感:三张仅包含一栋建筑物,分别位于建筑物 $$$1$$$、$$$2$$$ 和 $$$5$$$ 上,每张照片分别包含美丽 $$$-3$$$、$$$4$$$ 和 $$$7$$$,另一张照片包含建筑物 $$$3$$$ 和$$$4$$$,美丽$$$2$$$。
在第三个示例中,Alice 将只拍摄整个城市的一张照片。
在第四个示例中,Alice 可以拍摄以下照片以达到最大的美感:建筑物 $$$1$$$、$$$2$$$、$$$8$$$、$$$9$$$ 和 $$$10$$$ 上只有一栋建筑物的照片,以及建筑物 $$$3$$$、$$$4$$$、$$$5$$$、$$$6$$$ 和 $$$5$$$ 的单张照片$$$7$$$。