Score : $100$ points

Problem Statement

There are $N$ flowers arranged in a row. For each $i$ ($1 \leq i \leq N$), the height and the beauty of the $i$-th flower from the left is $h_i$ and $a_i$, respectively. Here, $h_1, h_2, \ldots, h_N$ are all distinct.

Taro is pulling out some flowers so that the following condition is met:

• The heights of the remaining flowers are monotonically increasing from left to right.

Find the maximum possible sum of the beauties of the remaining flowers.

Constraints

• All values in input are integers.
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq h_i \leq N$
• $h_1, h_2, \ldots, h_N$ are all distinct.
• $1 \leq a_i \leq 10^9$

Input

Input is given from Standard Input in the following format:

$N$

$h_1$ $h_2$ $\ldots$ $h_N$

$a_1$ $a_2$ $\ldots$ $a_N$

Output

Print the maximum possible sum of the beauties of the remaining flowers.

4
3 1 4 2
10 20 30 40

60

We should keep the second and fourth flowers from the left. Then, the heights would be $1, 2$ from left to right, which is monotonically increasing, and the sum of the beauties would be $20 + 40 = 60$.

1
1
10

10

The condition is met already at the beginning.

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

5000000000

The answer may not fit into a 32-bit integer type.

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

31

We should keep the second, third, sixth, eighth and ninth flowers from the left.