AT_pakencamp_2022_day2_e Harmony

パ研楽団には、 $ N $ 人の演奏者がいます。また、パ研楽団は $ M $ 種類の楽器を所有しています。 $ i $ 人目の演奏者の熟練度は $ A_i $ で担当楽器は $ B_i $ 、楽器の移行コストは $ C_i $ です。 $ 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) $ 行目には、 $ x = X_i $ としたときの答えを出力せよ。

### 小課題 1. ( $ 150 $ 点) $ N, Q \leq 2000 $ 2. ( $ 150 $ 点) $ M \leq 10 $ 3. ( $ 300 $ 点) 追加の制約はない ### Sample Explanation 1 例えば人 $ 2 $ の担当楽器を $ 2 $ に、人 $ 3 $ の担当楽器を $ 1 $ にすると調和度は $ 8 $ になります。このときかかるコストは $ C_2+C_3=6 $ です。 誰一人担当楽器を変えないと、調和度は $ 0 $ になります。このときかかるコストは $ 0 $ です。 ### Constraints - $ 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} $ - 入力は全て整数