AT_pakencamp_2022_day2_e Harmony

パ研楽団有 $N$ 名演奏者。此外，パ研楽团拥有 $M$ 种不同的乐器。第 $i$ 名演奏者的熟练度为 $A_i$，当前负责的乐器编号是 $B_i$，更换乐器所需的迁移代价为 $C_i$。每位演奏者都可以以 $C_i$ 的代价将负责的乐器更换为任意一种。 乐团的“调和度”定义如下： - 对于每种乐器，考虑所有负责该乐器的人的熟练度的最大值。$M$ 种乐器分别求得这 $M$ 个最大值后，取其中的最小值，作为调和度。若存在无人负责的乐器，则调和度为 $0$。 对于每个 $x = X_1, X_2, \ldots, X_Q$，请你求出，在总迁移代价不超过 $x$ 的前提下，能够实现的最大调和度。

输入按如下格式从标准输入读入： > $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$），第 $i$ 行输出当 $x = X_i$ 时的答案。

## 小子任务 1. ($150$ 分) $N, Q \leq 2000$ 2. ($150$ 分) $M \leq 10$ 3. ($300$ 分) 无额外限制 ## 样例解释 1 例如，将第 2 个人负责的乐器变更为 2，将第 3 个人负责的乐器变更为 1，此时调和度为 $8$。所需总代价为 $C_2+C_3=6$。 如果所有人都不更换负责的乐器，调和度为 $0$，此时总代价为 $0$。 # 约束条件 - $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}$ - 输入均为整数。 由 ChatGPT 5 翻译