分数: 100 点
问题陈述
有 N 花排成一排。 对于每个 i (1 \leq i \leq N),身高和美貌 i左数第朵花是 分别为 h_i 和 a_i。 在这里, h_1, h_2, \ldots, h_N 都是不同的。
太郎正在拔出一些花,以满足以下条件:
- 剩余花朵的高度从左到右单调增加。
找出剩余花朵的美丽程度的最大可能总和。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 2 × 10^5
- 1 \leq h_i \leq N
- h_1, h_2, \ldots, h_N 都是不同的。
- 1 \leq a_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N h_1 h_2 \ldots h_N a_1 a_2 \ldots a_N
输出
打印剩余花朵的最大可能的美丽总和。
示例输入 1
4 3 1 4 2 10 20 30 40
示例输出 1
60
我们应该保留左边的第二朵和第四朵花。 那么,高度将是 1, 2 从左到右,单调递增,美女的总和为 20 + 40 = 60.
示例输入 2
1 1 10
示例输出 2
10
条件一开始就已满足。
示例输入 3
5 1 2 3 4 5 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 3
5000000000
答案可能不适合 32 位整数类型。
示例输入 4
9 4 2 5 8 3 6 1 7 9 6 8 8 4 6 3 5 7 5
示例输出 4
31
我们应该保留左边的第二、第三、第六、第八和第九朵花。