AT_joigsp2025_i ティーパーティー (Tea Party)

葵计划举办一场茶会。预计包含葵在内共有 $M$ 人参加，所有参与者编号为 $1$ 到 $M$。葵打算给每位参与者分发 $1$ 块蛋糕和 $1$ 杯红茶。 为了茶会，葵准备了 $N$ 块蛋糕（$N \geq M$）和 $M$ 杯红茶。蛋糕编号为 $1$ 到 $N$，红茶编号为 $1$ 到 $M$。第 $i$ 块蛋糕（$1 \leq i \leq N$）的品牌为 $A_i$，美味度为 $B_i$。第 $j$ 杯红茶（$1 \leq j \leq M$）的品牌为 $C_j$，美味度为 $D_j$。葵希望分配蛋糕和红茶，使所有参与者的**幸福度**总和尽可能大。 若给第 $k$ 位参与者（$1 \leq k \leq M$）分配第 $i$ 块蛋糕（$1 \leq i \leq N$）和第 $j$ 杯红茶（$1 \leq j \leq M$），参与者 $k$ 的幸福度计算如下： - 若 $A_i = C_j$，则参与者 $k$ 的幸福度为 $B_i + D_j$。 - 若 $A_i \neq C_j$，则参与者 $k$ 的幸福度为 $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.（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 分）无额外约束。 --- ## 样例解释 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$）。 - 所有输入值均为整数。 由 ChatGPT 5 翻译