← 返回题目列表

AtCoder · dp_q

Q. 鲜花

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

分数: 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

我们应该保留左边的第二、第三、第六、第八和第九朵花。