Flowers

有一排花，共 $n$ 个，第 $i$ 个的高度是 $h_i$ ，权值是 $a_i$ ，保证高度互不相同。现在拿走一些花，使剩下的花高度单调递增，问剩下的花权值之和最大是多少。

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_q $ N $ 本の花が横一列に並んでいます。 各 $ i $ ($ 1\ \leq\ i\ \leq\ N $) について、左から $ i $ 番目の花の高さは $ h_i $ で、美しさは $ a_i $ です。 ただし、$ h_1,\ h_2,\ \ldots,\ h_N $ はすべて相異なります。 太郎君は何本かの花を抜き去ることで、次の条件が成り立つようにしようとしています。 - 残りの花を左から順に見ると、高さが単調増加になっている。 残りの花の美しさの総和の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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
1
10

10

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

5000000000

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

31

### 制約 - 入力はすべて整数である。 - $ 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 $ ### Sample Explanation 1 左から $ 2,\ 4 $ 番目の花を残せばよいです。 すると、高さは左から順に $ 1,\ 2 $ となり、単調増加になっています。 また、美しさの総和は $ 20\ +\ 40\ =\ 60 $ となります。 ### Sample Explanation 2 最初から条件が成り立っています。 ### Sample Explanation 3 答えは 32-bit 整数型に収まらない場合があります。 ### Sample Explanation 4 左から $ 2,\ 3,\ 6,\ 8,\ 9 $ 番目の花を残せばよいです。