题目描述

葵计划举办一场茶话会，共有包括葵在内的 $M$ 位参与者，编号为 $1$ 到 $M$。葵打算给每位参与者分发一块蛋糕和一杯红茶。

为此，葵准备了 $N$ 块蛋糕（编号 $1$ 到 $N$）和 $M$ 杯红茶（编号 $1$ 到 $M$），其中 $N \geq M$。蛋糕 $i$（$1 \leq i \leq N$）的品牌是 $A_i$，美味度是 $B_i$。红茶 $j$（$1 \leq j \leq M$）的品牌是 $C_j$，美味度是 $D_j$。

葵希望通过合理分配蛋糕和红茶，最大化所有参与者的幸福度总和。

分配规则如下：

葵会从 $N$ 块蛋糕中选择 $M$ 块分配给参与者（剩余蛋糕由葵在其他时间食用，不影响幸福度）。当参与者获得蛋糕 $i$ 和红茶 $j$ 时，其幸福度计算方式为：

• 若蛋糕与红茶品牌相同（$A_i = C_j$），则幸福度为 $B_i + D_j$。
• 若品牌不同（$A_i \neq C_j$），则幸福度为 $B_i$。

请计算通过优化分配蛋糕和红茶，所有参与者幸福度总和的最大值。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$
$C_1$ $C_2$ $\cdots$ $C_M$
$D_1$ $D_2$ $\cdots$ $D_M$

输出格式

输出一行，表示葵合理分配准备的蛋糕和红茶时，所有参与者幸福度总和的最大值。

4 3
1 1 2 3
2 1 2 4
1 1 2
3 1 1

12

5 3
1 2 3 4 5
4695 53325 57544 74342 81986
1 2 3
59037 23296 16434

232949

4 3
2 1 3 1
52 49 72 31
3 1 3
0 0 0

173

5 2
1 1 2 3 5
0 0 0 0 0
1 1
3 1

4

提示

【样例解释 #1】

葵可以按以下方式分配蛋糕和红茶，使所有参与者的幸福度总和达到最大值 $12$：

• 参与者 $1$ 获得蛋糕 $1$ 和红茶 $1$，幸福度为 $2 + 3 = 5$。
• 参与者 $2$ 获得蛋糕 $3$ 和红茶 $3$，幸福度为 $2 + 1 = 3$。
• 参与者 $3$ 获得蛋糕 $4$ 和红茶 $2$，幸福度为 $4$。

无论如何分配，所有参加者的幸福度总和都不会超过 $12$，因此输出 $12$。

该样例满足子任务 $4$ 的限制。

【样例解释 #2】

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

【样例解释 #3】

该样例满足子任务 $1,4$ 的限制。

【样例解释 #4】

该样例满足子任务 $2,4$ 的限制。

【数据范围】

• $1 \leq M \leq N \leq 200\,000$。
• $1 \leq A_i \leq N$（$1 \leq i \leq N$）。
• $0 \leq B_i \leq 10^9$（$1 \leq i \leq N$）。
• $1 \leq C_j \leq N$（$1 \leq j \leq M$）。
• $0 \leq D_j \leq 10^9$（$1 \leq j \leq M$）。
• 输入的所有值都是整数。

【子任务】

1. （$8$ 分）$D_j = 0$（$1 \leq j \leq M$）。
2. （$19$ 分）$B_i = 0$（$1 \leq i \leq N$）。
3. （$31$ 分）$A_i = i$（$1 \leq i \leq N$），$C_j = j$（$1 \leq j \leq M$）。
4. （$42$ 分）无附加限制。