日本情報オリンピック 第5回 女性部門

2025年2月8日
情報オリンピック日本委員会

問題文

2N 枚のカードが机の上に横一列に並んでおり，左から順に 1, 2, …, 2N の番号が付けられている．カード i (1 ≦ i ≦ 2N) には整数 A_i が書かれている．各 x = 1, 2, …, N について，整数 x が書かれたカードはちょうど 2 枚存在する．

ビーバーのビ太郎は，これらのカードを用いて 神経衰弱 と呼ばれるゲームを行う．ビ太郎は，右手と左手に 1 枚ずつカードを持つことができる．
神経衰弱 は以下の手順で行われる．

• i = 1, 2, …, 2N の順に以下を行う．
  1. ビ太郎は，カード i を拾うか拾わないかを選ぶ．カードを拾おうとする場合，以下の 2. から 5. が順に起こる．カードを拾わない場合，以下の 2. から 5. はスキップする．
  2. 整数 A_i が書かれたカードをビ太郎が持っているならば，そのカードと机の上にあるカード i は消滅し，ビ太郎は V_Ai の点数を得る．
  3. ビ太郎が左手にカードを持っているならば，そのカードを捨てる．
  4. ビ太郎が右手にカードを持っているならば，そのカードを左手に移す．
  5. カード i が存在する（消滅していない）ならば，ビ太郎は右手でカード i を持つ．

これらの手順で得た点数の合計が最終的なビ太郎のスコアとなる．ビ太郎は，このゲームで得ることのできるスコアの最大値を知りたい．

カードの並びと各整数に割り当てられた点数の情報が与えられたとき，ビ太郎が得ることのできるスコアの最大値を求めるプログラムを作成せよ．

制約

• 1 ≦ N ≦ 400 000．
• (A₁, A₂, …, A_2N) は (1, 1, 2, 2, …, N, N) の並べ替えである．
• 1 ≦ V_k ≦ 10⁹ (1 ≦ k ≦ N)．
• 入力される値はすべて整数である．

小課題

1. (8 点) (A₁, A₂, …, A_N) = (1, 2, …, N)，N ≦ 5 000．
2. (12 点) (A₁, A₂, …, A_N) = (1, 2, …, N)．
3. (6 点) N ≦ 9．
4. (9 点) N ≦ 18．
5. (16 点) N ≦ 300．
6. (18 点) N ≦ 3 000．
7. (18 点) N ≦ 150 000，V_k = 1 (1 ≦ k ≦ N)．
8. (8 点) N ≦ 150 000．
9. (5 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N
A₁ A₂ … A_2N
V₁ V₂ … V_N

出力

ビ太郎が得ることのできるスコアの最大値を出力せよ．

入出力例

入力例 1
3
1 2 3 1 2 3
5 2 8

出力例 1
13

ビ太郎は以下の手順でスコア 13 を得ることができる．

1. カード 1 を拾おうとする．カード 1 には整数 1 が書かれている．ビ太郎は整数 1 が書かれたカードを持っていないから，カードの消滅は起こらない．ビ太郎は右手にカード 1 を持った状態になる．
2. カード 2 は拾わずスキップする．
3. カード 3 を拾おうとする．カード 3 には整数 3 が書かれている．ビ太郎は整数 3 が書かれたカードを持っていないから，カードの消滅は起こらない．ビ太郎は左手にカード 1 を，右手にカード 3 を持った状態になる．
4. カード 4 を拾おうとする．カード 4 には整数 1 が書かれている．ビ太郎は整数 1 の書かれたカード 1 を持っているから，左手に持ったカード 1 と机の上のカード 4 は消滅し，ビ太郎は V₁ = 5 の点数を得る．その後，ビ太郎は左手にカード 3 を持った状態になる．
5. カード 5 は拾わずスキップする．
6. カード 6 を拾おうとする．カード 6 には整数 3 が書かれている．ビ太郎は整数 3 の書かれたカード 3 を持っているから，左手に持ったカード 3 と机の上のカード 6 は消滅し，ビ太郎は V₃ = 8 の点数を得る．その後，ビ太郎はどちらの手にもカードを持っていない状態になる．

ビ太郎は 13 より大きいスコアを得ることはできないため，13 を出力する．

この入力例は小課題 1, 2, 3, 4, 5, 6, 8, 9 の制約を満たす．

入力例 2
4
1 2 1 2 3 4 4 3
39 62 55 21

出力例 2
156

ビ太郎は，例えばカード 1, 2, 3, 4, 5, 6, 8 を拾おうとすることで，スコア V₁ + V₂ + V₃ = 156 を得ることができる．

ビ太郎は 156 より大きいスコアを得ることはできないため，156 を出力する．

この入力例は小課題 3, 4, 5, 6, 8, 9 の制約を満たす．

入力例 3
10
7 2 5 8 4 10 8 2 7 5 6 3 4 1 10 9 9 1 6 3
185163245 734376902 849123714 97860221 844860642 689054872 471545587 607735137 664633003 831663829

出力例 3
3117416130

この入力例は小課題 4, 5, 6, 8, 9 の制約を満たす．

入力例 4
15
4 3 8 3 10 15 14 1 12 4 13 1 6 7 10 15 2 8 12 2 9 11 11 13 5 9 14 5 6 7
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 4
6

この入力例は小課題 4, 5, 6, 7, 8, 9 の制約を満たす．