Description

海狸哈利经营着一家旅馆，在接下来的 $Q$ 周内，他必须在每个星期天晚上清洗床单，直到旅游季结束。在第 $j$ 周，他需要晾干 $N$ 条刚洗好的床单，他会把它们挂在两根平行的、长度均为 $L_j$ 的晾衣绳上。床单可以相邻悬挂，但不能重叠。每条床单的宽度为 $d_i$ 个单位，并且因为床单非常长，所以它总是会以宽度 $d_i$ 的方式占据晾衣绳的空间。床单的晾干时间与大小无关，而是由材质决定的。具体来说，第 $i$ 条床单如果只挂在一根绳子上需要 $t_i^{\text{slow}}$ 分钟才能晾干；如果同时横跨两根绳子，则可以更快地晾干，仅需 $t_i^{\text{fast}}$ 分钟，但这会同时占用两根绳子上的空间。为了避免床单发霉，哈利必须在洗完后立即把所有床单挂起来，也就是说，所有床单必须同时挂上去。

哈利想在周日尽快睡觉，因此他希望你帮忙确定在每一周 $j$ 中完成晾干所需的最短时间，或者告诉他该周无法完成晾干。

Input Format

第一行包含两个整数 $N$ 和 $Q$，分别表示床单数量和直到旅游季结束的周数。
接下来的 $N$ 行中，每行包含三个整数 $d_i, t_i^{\text{fast}}, t_i^{\text{slow}}$，分别表示第 $i$ 条床单的宽度、较快的晾干时间和较慢的晾干时间。
最后的 $Q$ 行，每行包含一个整数 $L_j$，表示第 $j$ 周每根晾衣绳的长度。

Output Format

输出 $Q$ 行，其中第 $j$ 行表示第 $j$ 周完成晾干所需的最短时间。如果无法在该周晾干所有床单，则输出 -1。

3 3
1 2 2
1 1 4
2 3 100
3
1
4

4
-1
3

Hint

输入限制

• $1 \leq N \leq 3 \cdot 10^4$
• $1 \leq Q \leq 3 \cdot 10^5$
• 对所有 $1 \leq i \leq N$，有 $1 \leq d_i \leq 3 \cdot 10^5$
• 对所有 $1 \leq i \leq N$，有 $1 \leq t_i^{\text{fast}} \leq t_i^{\text{slow}} \leq 10^9$
• 对所有 $1 \leq j \leq Q$，有 $1 \leq L_j \leq 3 \cdot 10^5$

翻译由 ChatGPT-5 完成