配点 : 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}
- 所有输入均为整数
小課題
- (150 点) N, Q \leq 2000
- (150 点) M \leq 10
- (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