← 返回题目列表

AtCoder · joigsp2025_i

I. 茶会

中文机器翻译题面 查看原题

配点: 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).
  • 所有输入值都是整数。

小課題

  1. (8 点) D_j = 0 (1 \leqq j \leqq M).
  2. (19 点) B_i = 0 (1 \leqq i \leqq N).
  3. (31 点) A_i = i (1 \leqq i \leqq N),C_j = j (1 \leqq j \leqq M).
  4. (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 。