花朵选拔(Flowers)

题目描述

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

输出格式

残りの花の美しさの総和の最大値を出力せよ。

样例输入 #1

4
3 1 4 2
10 20 30 40

样例输出 #1

60

样例输入 #2

1
1
10

样例输出 #2

10

样例输入 #3

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

样例输出 #3

5000000000

样例输入 #4

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

样例输出 #4

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$ 番目の花を残せばよいです。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1500。

测试点分布

出处：原题链接