AT_oupc2023_day1_n Bench

有一张很长的长椅，上面一排放着 $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 翻译