Q - Flowers Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

左から 2, 4 番目の花を残せばよいです。 すると、高さは左から順に 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-bit 整数型に収まらない場合があります。

入力例 4

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

出力例 4

31

左から 2, 3, 6, 8, 9 番目の花を残せばよいです。

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 × 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.

Sample Input 1

4
3 1 4 2
10 20 30 40

Sample Output 1

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.

Sample Input 2

1
1
10

Sample Output 2

10

The condition is met already at the beginning.

Sample Input 3

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5000000000

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

Sample Input 4

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

Sample Output 4

31

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