问题陈述

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

输出

打印剩余花朵的最大可能美值总和。

4
3 1 4 2
10 20 30 40

60

我们应该保留从左边开始的第二朵花和第四朵花。那么，从左到右的高度为 $1, 2$ ，单调递增，美观度总和为 $20 + 40 = 60$ 。

1
1
10

10

开始时已满足条件。

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

5000000000

答案可能不适合 32 位整数类型。

9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5

31

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

来源

https://atcoder.jp/contests/dp/tasks/dp_q