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 翻译