有一张很长的长椅，上面一排放着 $L$ 个编号分别为 $1$ 到 $L$ 的坐垫。对于每一个 $i$（$1\leq i\leq L-1$），坐垫 $i$ 与坐垫 $i+1$ 是相邻的。

现在有 $N$ 个小组依次前来坐在长椅上。第 $j$ 个小组有 $A_j$ 个人，该小组会选择一段连续的 $A_j$ 个坐垫（即对于某个 $p$，选择坐垫 $p,p+1,\dots,p+A_j-1$），并每个坐垫坐一个人。如果找不到一段连续的 $A_j$ 个坐垫且这段坐垫没有其他人坐，且每个人都能入座，这个小组就入座失败。一旦有一个小组入座失败，后面的小组都不会再来坐了。

在第 $1$ 个小组开始前，KowerKoint 君可以花钱调整各个小组人数，具体操作如下，可以任意次数进行（可以不进行）：

• 支付 $B_j$ 元，将第 $j$ 个小组的人数减少 $1$（仅当该组人数 $\geq 2$ 时才可进行）
• 支付 $C_j$ 元，将第 $j$ 个小组的人数增加 $1$

但在操作过程中以及操作后，所持金钱不能为负数。并且，$B_j$ 可以为负数，$-x$ 元意味着可以获得 $x$ 元。

请考虑，对于任意能让每组在选择座位时，最终必然能够入座的人数之和最大值为多少，也就是追求最大的 $y$，使得无论每组如何选择座位，至少 $y$ 个人必然能入座。现在给出 $Q$ 个操作前所持金钱 $M_1,M_2,\dots,M_Q$，对于每个 $k$（$1\leq k\leq Q$），问当持有 $M_k$ 元时，KowerKoint 君能通过操作使得总入座人数最大是多少。

输入从标准输入获得，格式如下所示。

$N$ $L$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_N$ $B_N$ $C_N$
$Q$
$M_1$
$M_2$
$\vdots$
$M_Q$

请输出 $Q$ 行，第 $k$ 行输出当初始持有 $M_k$ 元时，KowerKoint 君经过操作后，无论如何坐人，一定能够坐下的最大人数。

子任务

1. （1分）$B_j=1,C_j=1,Q=1,M_k=0$
2. （99分）无额外限制

样例解释 1

• 第 1 个查询，KowerKoint 君有 0 元。如果不操作，只有第 1 个小组的 2 个人一定能坐下。第 3 个小组人数可以任意增加，但这无法让一定能坐下的人数增加。
• 第 2 个查询，KowerKoint 君有 1 元。花 1 元将第 2 个小组人数减少 1，前 2 个小组的 2+3=5 人都能一定入座，这是最大值。
• 第 3 个查询，KowerKoint 君有 5 元。花 1 元将第 2 个小组人数减少 1，花 3 元将第 3 个小组人数减少 1，则 2+3+1=6 人全部一定能入座，这是最大。
• 第 4 个查询，KowerKoint 君有 10 元。花 $2\times5=10$ 元将第 1 个小组人数增加 5，则第 1 个小组的 7 个人都能一定入座，这是最大。

该测试用例不满足子任务 1 的限制。

样例解释 2

该测试用例满足子任务 1 的限制。

样例解释 3

该测试用例不满足子任务 1 的限制。

数据范围与限制

• $1 \leq N \leq L \leq 3000$
• $1 \leq A_j \leq L$
• $-10^9 \leq B_j \leq 10^9$
• $0 \leq C_j \leq 10^9$
• $1 \leq B_j+C_j$
• $1 \leq Q \leq 200\,000$
• $0 \leq M_k \leq 10^{15}$
• 所有输入均为整数。

由 ChatGPT 5 翻译