Max Increasing Subsequence

2 secs 1024 MB
shogo314's icon shogo314

問題文

長さ NN の配列 A,BA, B が与えられます。

  • l=k|l| = k
  • l1<l2<<lkl_1 < l_2 < \cdots < l_k
  • Al1<Al2<<AlkA_{l_1} < A_{l_2} < \cdots < A_{l_k}
  • 1kN1 \leq k \leq N

となるように ll を選択します。このときの

i=1kBli\sum_{i=1}^{k} B_{l_i}

の最大値を求めてください。

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Ai2×105,(1iN)1 \leq A_i \leq 2 \times 10^5,\quad(1 \leq i \leq N)
  • 1Bi109,(1iN)1 \leq B_i \leq 10^9,\quad(1 \leq i \leq N)

入力

入力は以下の形式で標準入力から与えられる。

NN
A1A_1 A2A_2 \dots ANA_N
B1B_1 B2B_2 \dots BNB_N

出力

答えを 11 行で出力せよ。

入力例 1

4
2 1 3 4
2 3 2 1

出力例 1

6

入力例 2

5
4 5 6 1 2
1 1 1 2 2

出力例 2

4

Submit


Go (1.21)