← 返回题目列表

AtCoder · pakencamp_2022_day2_e

E. 和谐

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

配点 : 600 点

問題文

公园管弦乐团有 有 N 表演者。此外,帕肯管弦乐团 我拥有 M 种乐器。i 第二个表演者的技能等级是 A_i 负责的仪器是 B_i 转移仪器的费用为 C_i 。i 第二位表演者是 您可以将仪器更改为您喜欢的任何仪器,迁移成本为 C_i 。

管弦乐队的和谐程度定义如下。

  • M 对于每种类型的仪器,请考虑该仪器负责人的最高熟练程度。这个 M 值的最小值是和谐程度。然而,如果有一种乐器无人负责,那么和谐的程度就会降低。 对于 0 。

x = X_1, X_2, \ldots ,X_Q ,总迁移成本为 找出在不超过 x 的情况下可以达到的最大和谐度。

制約

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
  • 1 \leq B_i \leq M \ (1 \leq i \leq N)
  • 0 \leq C_i \leq 10^9 \ (1 \leq i \leq N)
  • 0 \leq X_1 < X_2 < \cdots < X_Q \leq 2 \times 10^{14}
  • 所有输入均为整数

小課題

  1. (150 点) N, Q \leq 2000
  2. (150 点) M \leq 10
  3. (300 点)无附加约束 输出

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N
Q
X_1 X_2 \ldots X_Q

出力

Q 行。 当i \ (1 \leq i \leq Q) 行中, x = X_i 时打印答案。


入力例 1

5 3
7 1 4
10 3 3
8 3 3
9 3 5
7 1 4
6
2 9 12 15 25 46

出力例 1

0
8
8
8
8
8

例如,人们 2 的仪器 2 ,人 当设置 3 的仪器 1 时,和谐度为 8 。此时的成本为 C_2+C_3=6 。

如果没有人更换负责的乐器,和谐度就会下降。 0 。此时的成本为 0 。


入力例 2

10 6
10 3 4
12 2 5
2 1 3
7 3 15
12 1 10
8 3 3
11 3 14
13 6 9
3 3 12
4 5 1
10
1 3 7 37 53 85 88 91 94 148

出力例 2

0
4
8
8
8
8
8
8
8
8