题目描述

有 $N$ 朵花排成一行。对于每朵花 $i$ ($1 \leq i \leq N$)，从左往右数的高度和美丽程度分别为 $h_i$ 和 $a_i$，其中 $h_1, h_2, \ldots, h_N$ 互不相同。

Taro 想要拔掉一些花，使得剩下的花满足以下条件：

• 剩下的花的高度从左到右单调递增。

计算剩下的花的美丽程度的最大可能总和。

约束条件

• 输入中的所有值均为整数。
• $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

我们应该保留从左往右数的第二、第三、第六、第八和第九朵花。