题目描述

塔尖俱乐部计划举办一场茶话会，共有 $m$ 位参与者，编号为 $1$ 到 $m$。塔尖俱乐部打算给每位参与者分发一块蛋糕和一杯红茶。

为此，塔尖俱乐部准备了 $n$ 块蛋糕和 $m$ 杯红茶，其中 $n \geq m$。蛋糕 $i$ 的品牌是 $a_i$，美味度是 $b_i$。红茶 $i$ 的品牌是 $c_i$，美味度是 $d_i$。

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

分配规则如下：

塔尖俱乐部会从 $n$ 块蛋糕中选择 $m$ 块分配给参与者（剩余蛋糕不影响幸福度）。当参与者获得蛋糕 $i$ 和红茶 $j$ 时，其幸福度计算方式为：

• 若蛋糕与红茶品牌相同（$a_i = c_j$），则幸福度为 $b_i + d_j$。
• 若品牌不同（$a_i \neq c_j$），则幸福度为 $b_i$。

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

输入格式

第一行输入 $n,m$ 代表蛋糕和茶的数量。

• 接下来一行输入 $n$ 个整数为 $a_1,a_2,\ldots,a_n$ 代表每一块蛋糕的品牌。
• 接下来一行输入 $n$ 个整数为 $b_1,b_2,\ldots,b_n$ 代表每一块蛋糕的美味度。
• 接下来一行输入 $m$ 个整数为 $c_1,c_2,\ldots,c_m$ 代表每一杯茶的品牌。
• 接下来一行输入 $m$ 个整数为 $d_1,d_2,\ldots,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$。

数据范围

对于 $100\%$ 的数据满足：$1 \leq m \leq n \leq 2\times 10^5$。$1 \leq a_i, \leq n$，$0 \leq b_i \leq 10^9$。$1 \leq c_j \leq n$，$0 \leq d_j \leq 10^9$。

• 子任务 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$ 分）无附加限制。