← 返回题目列表

Codeforces · 1482/E

E. 天际线照片

中文机器翻译题面 查看原题

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