配点: 100 点
葵计划举办茶会。 这次茶会包括葵。 M 人们正计划参加,并且参与者已 它们的编号最大为 1 我决定将所有值添加到 M 。 葵告诉每位参与者,1 配一片蛋糕 1 我要去递茶。
为了茶会,葵 N 一块蛋糕(N \geqq M)和 M 我准备了一杯茶。 为了蛋糕 1 我决定将所有值添加到 N 直到,红茶已经 它们的编号最大为 1 我决定将所有值添加到 M 。 蛋糕 i (1 \leqq i \leqq N)品牌是 A_i 而且味道是 B_i 。 红茶 j (1 \leqq j \leqq M)品牌是 C_j 而且味道是 D_j 。 葵是参与者 我想向参与者分发蛋糕和茶,以便 幸福度 的总和变得尽可能大。 参与者 k (1 \leqq k \leqq M)蛋糕 i (1 \leqq i \leqq N)和红茶 j (1 \leqq j \leqq 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 行。
制約
- 1 \leqq M \leqq N \leqq 200\,000.
- 1 \leqq A_i \leqq N (1 \leqq i \leqq N).
- 0 \leqq B_i \leqq 10^9 (1 \leqq i \leqq N).
- 1 \leqq C_j \leqq N (1 \leqq j \leqq M).
- 0 \leqq D_j \leqq 10^9 (1 \leqq j \leqq M).
- 所有输入值都是整数。
小課題
- (8 点) D_j = 0 (1 \leqq j \leqq M).
- (19 点) B_i = 0 (1 \leqq i \leqq N).
- (31 点) A_i = i (1 \leqq i \leqq N),C_j = j (1 \leqq j \leqq M).
- (42 点)没有额外的限制。
入力例 1
4 3 1 1 2 3 2 1 2 4 1 1 2 3 1 1
出力例 1
12
当葵适当地分发她准备的蛋糕和茶时,所有参与者的最大幸福总和是 12 。
- 参加者 1 蛋糕 1 和红茶 分发 1 。参与者 1 的幸福水平是 2 + 3 = 5 。
- 参加者 2 蛋糕 3 和红茶 分发 3 。参与者 2 的幸福水平是 2 + 1 = 3 。
- 参加者 3 蛋糕 4 和红茶 分发 2 。参与者 3 的幸福水平是 4 。
无论你如何分配,所有参与者的总幸福水平将为 由于它不能大于 12 ,12 输出该值。
此输入示例是一个小作业。 4 。
入力例 2
5 3 1 2 3 4 5 4695 53325 57544 74342 81986 1 2 3 59037 23296 16434
出力例 2
232949
此输入示例是一个小作业。 3,4 。
入力例 3
4 3 2 1 3 1 52 49 72 31 3 1 3 0 0 0
出力例 3
173
此输入示例是一个小作业。 1,4 。
入力例 4
5 2 1 1 2 3 5 0 0 0 0 0 1 1 3 1
出力例 4
4
此输入示例是一个小作业。 2,4 。