P13737 [JOIGST 2025] 茶话会 / Tea Party

葵计划举办一场茶话会，共有包括葵在内的 $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$

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

#### 【样例解释 #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$ 分）无附加限制。