You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $2N$ 张卡牌从左到右依次放在桌子上，编号为 $1,2,\ldots,2N$，卡牌 $i$ 上写有整数 $A_i$。对于 $x=1,2,\ldots,N$，存在恰好两张卡牌上写的整数为 $x$。

海狸比太郎决定用这些卡牌玩一个叫做“神经衰弱”的游戏；该游戏的流程如下：

• 依次考虑卡牌 $i=1,2,\ldots,2N$：
  1. 比太郎决定是否拿起这张卡牌：如果他决定拿起，那么依次进行以下的步骤 2 至步骤 5；如果他决定不拿起（跳过该卡牌），则跳过以下的步骤；
  2. 如果比太郎的手中持有一张写有 $A_i$ 的卡牌，那么该卡牌和卡牌 $i$ 同时消失，他获得 $V_{A_i}$ 分；
  3. 如果比太郎左手中有一张卡牌，那么他将其丢弃；
  4. 如果比太郎右手中有一张卡牌，那么他将其转移到左手；
  5. 如果卡牌 $i$ 没有在步骤 2 中消失，那么他将其放在右手中。

通过上面的流程，每次得到的分数之和即为比太郎的最终得分。

请求出比太郎能获得的最大得分。

输入格式

第一行输入一个整数 $N$。

第二行输入 $2N$ 个整数 $A_1,A_2,\ldots,A_{2N}$。

第三行输入 $N$ 个整数 $V_1,V_2,\ldots,V_N$。

输出格式

输出一行一个整数，表示最大得分。

3
1 2 3 1 2 3
5 2 8

13

4
1 2 1 2 3 4 4 3
39 62 55 21

156

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

3117416130

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

6

提示

【样例解释 #1】

比太郎可以通过以下流程获得分数 $13$：

1. 拿起卡牌 $1$，该卡牌上面写着 $1$；由于比太郎没有其他写着 $1$ 的纸牌，所以他将其放在右手中；
2. 跳过卡牌 $2$；
3. 拿起卡牌 $3$，该卡牌上面写着 $3$；由于比太郎没有其他写着 $3$ 的纸牌，所以卡牌 $1$ 从右手转移到了左手，他将卡牌 $3$ 放在右手中；
4. 拿起卡牌 $4$，该卡牌上面写着 $1$；由于卡牌 $1$ 上也写着 $1$，所以两张牌都消失了，他获得 $V_1=5$ 分，卡牌 $3$ 则从右手转移到了左手；
5. 跳过卡牌 $5$；
6. 拿起卡牌 $6$，该卡牌上面写着 $3$；由于卡牌 $3$ 上也写着 $3$，所以两张牌都消失了，他获得 $V_3=8$ 分，此时他两只手上都没有任何卡牌了。

可以证明这是最优的。

该样例满足子任务 $1,2,3,4,5,6,8,9$ 的限制。

【样例解释 #2】

比太郎可以通过拿起卡牌 $1,2,3,4,5,6,8$ 来获得分数 $V_1+V_2+V_3=156$。可以证明这是最优的。

该样例满足子任务 $3,4,5,6,8,9$ 的限制。

【样例解释 #3】

该样例满足子任务 $4,5,6,8,9$ 的限制。

【样例解释 #4】

该样例满足子任务 $4,5,6,7,8,9$ 的限制。

【数据范围】

• $1\le N\le 4\times 10^5$；
• $A_1,A_2,\ldots,A_{2N}$ 中，对于 $x=1,2,\ldots,N$，$x$ 正好出现两次；
• $1\le V_k\le 10^9$。

【子任务】

1. （$8$ 分）$(A_1,A_2,\ldots,A_N)=(1,2,\ldots,N)$，$N\le 5000$；
2. （$12$ 分）$(A_1,A_2,\ldots,A_N)=(1,2,\ldots,N)$；
3. （$6$ 分）$N\le 9$；
4. （$9$ 分）$N\le 18$；
5. （$16$ 分）$N\le 300$
6. （$18$ 分）$N\le 3000$；
7. （$18$ 分）$N\le 1.5\times 10^5$，$V_k\le 1(1\le k\le N)$；
8. （$8$ 分）$N\le 1.5\times 10^5$；
9. （$5$ 分）无附加限制。