AT_joig2025_e.神経衰弱 2 (Pair Matching 2)

桌面上横向排列着 $2N$ 张卡牌，从左到右依次编号为 $1, 2, \dots, 2N$。卡牌 $i$（$1 \leq i \leq 2N$）上写有一个整数 $A_i$。对于每个 $x=1,2,\dots,N$，数字 $x$ 恰好出现在两张卡牌上。

比太郎将用这些卡牌进行名为神经衰弱的游戏。比太郎可以用左手和右手各持一张卡牌。

“神经衰弱”游戏的步骤如下：

• 按照 $i=1,2,\dots,2N$ 的顺序，依次进行以下操作：
  1. 比太郎选择是否要拿起第 $i$ 张卡牌。如果不拿，则跳过第2~5步。
  2. 如果比太郎手中有写有 $A_i$ 的卡牌，则他手中的那张卡牌与桌上的第 $i$ 张卡牌都会消失，比太郎获得 $V_{A_i}$ 的分数。
  3. 如果比太郎左手持有卡牌，则弃掉左手的卡牌。
  4. 如果比太郎右手持有卡牌，则将其移到左手。
  5. 若第 $i$ 张卡牌还在（未消失），比太郎用右手拿起第 $i$ 张卡牌。

通过上述过程获得的分数之和就是比太郎的最终得分。比太郎想知道，在本局游戏中，他最多能获得多少分。

给定卡牌的排列和每个整数分数的信息，请你编程输出比太郎能获得的最大分数。

输入按以下格式给出：

$N$ $A_1$ $A_2$ $\cdots$ $A_{2N}$ $V_1$ $V_2$ $\cdots$ $V_N$

输出比太郎能够获得的最大分数。

子任务

1. （8 分）$(A_1, A_2, \dots, A_N) = (1, 2, \dots, N)$，$N \leq 5000$。
2. （12 分）$(A_1, A_2, \dots, A_N) = (1, 2, \dots, N)$。
3. （6 分）$N \leq 9$。
4. （9 分）$N \leq 18$。
5. （16 分）$N \leq 300$。
6. （18 分）$N \leq 3\,000$。
7. （18 分）$N \leq 150\,000$，$V_k = 1$（$1 \leq k \leq N$）。
8. （8 分）$N \leq 150\,000$。
9. （5 分）无其他额外限制。

样例解释 1

比太郎可以通过如下操作获得 $13$ 分：

1. 拿起第1张卡牌。此卡牌写着数字1，比太郎手里没有写着1的卡牌，因此没有卡牌消失。此时右手持第1张卡牌。
2. 跳过第2张卡牌，不拿。
3. 拿起第3张卡牌。该卡牌写着数字3，比太郎手里没有写着3的卡牌。此时左手持第1张，右手持第3张卡牌。
4. 拿起第4张卡牌。该卡牌写着数字1，比太郎左手持有写着1的第1张卡牌。左手的第1张卡牌和桌上第4张卡牌消失，比太郎获得 $V_1=5$ 分。之后左手仅持第3张卡牌。
5. 跳过第5张卡牌，不拿。
6. 拿起第6张卡牌。该卡牌写着数字3，比太郎左手持有写着3的第3张卡牌。左手的第3张卡牌和桌上第6张卡牌消失，比太郎获得 $V_3=8$ 分。此后双手皆无卡牌。

比太郎无法获得大于 $13$ 的分数，因此输出 $13$。

本样例满足子任务 $1,2,3,4,5,6,8,9$ 的约束。

样例解释 2

比太郎可以选择依次拿起第 $1,2,3,4,5,6,8$ 张卡牌，获得分数 $V_1+V_2+V_3=156$。

比太郎无法获得大于 $156$ 的分数，因此输出 $156$。

本样例满足子任务 $3,4,5,6,8,9$ 的约束。

样例解释 3

本输入样例满足子任务 $4,5,6,8,9$ 的约束。

样例解释 4

本输入样例满足子任务 $4,5,6,7,8,9$ 的约束。

数据范围与限制

• $1 \leq N \leq 400\,000$。
• $(A_1, A_2, \dots, A_{2N})$ 是 $(1,1,2,2,\dots,N,N)$ 的一个排列。
• $1 \leq V_k \leq 10^9$（$1 \leq k \leq N$）。
• 所有输入均为整数。

由 ChatGPT 5 翻译