勇者比太郎正在挑战守护村庄免受怪兽袭击的防御战任务。防御战的难度用一个介于 $1$ 到 $L$ 的整数表示，这个值可以在挑战时自由选择。难度为 $\ell$（$1 \leq \ell \leq L$）的防御战中，出现的怪兽的 HP 是（难度为 $1$ 时的基准）$\ell$ 倍。

防御战持续 $T$ 秒，共有 $N$ 只怪兽依次出现。每只怪兽编号为 $1$ 至 $N$。从防御战开始后 $t$ 秒（$0 \leq t \leq T$）的时刻称为时刻 $t$。编号为 $i$ 的怪兽（$1 \leq i \leq N$）会在时刻 $S_i$（$0 \leq S_i < T$）出现，其强度为 $P_i$，HP 则为难度为 $\ell$ 时 $\ell \times H_i$。

防御战中，比太郎可以不限次数地进行如下操作：

• 从当前出现的怪兽中选出一只，花费 $1$ 秒对其攻击一次，该怪兽的 HP 减少 $1$。HP 变为 $0$ 的怪兽会被击败，之后无法再对其进行攻击。

当时刻 $T$ 到来时防御战结束，随后按如下方式计算防御战的评价值：

• 记在时刻 $T$ 结束后，编号为 $i$ 的怪兽的 HP 为 $h_i$，则评价值为 $h_1 P_1 + h_2 P_2 + \dots + h_N P_N$。

当且仅当评价值不超过任务规定的基准值 $m$ 时，比太郎才能完成该任务。

由于完成高难度的任务可获得更丰厚的奖励，比太郎想求出自己能完成任务的最大难度。然而，基准值事先未知，因此比太郎需要针对 $Q$ 个候选基准值 $M_1, M_2, \dots, M_Q$，逐一求出每个基准值下他能够完成任务的最大难度。

现给定防御战的信息和基准值的候选列表，请对于每个基准值，判断比太郎是否可以完成任务，若可完成，请给出他能完成任务的最大难度。

---

输入以以下格式从标准输入给出。

$N$ $L$ $T$
$S_1$ $H_1$ $P_1$
$S_2$ $H_2$ $P_2$
$\vdots$
$S_N$ $H_N$ $P_N$
$Q$
$M_1$
$M_2$
$\vdots$
$M_Q$

请输出 $Q$ 行，第 $j$ 行（$1 \leq j \leq Q$）输出，当 $m = M_j$ 时，能够完成任务的最大难度。如果任何难度下都无法完成任务，则输出 0。

小子任务

1. （$1$ 分）$N \leq 30$，$Q = 1$，$M_1 = 0$，$L = 1$。
2. （$3$ 分）$N \leq 30$，$Q = 1$，$M_1 = 0$。
3. （$10$ 分）$N \leq 30$，$Q \leq 3$。
4. （$10$ 分）$Q \leq 3$。
5. （$35$ 分）$N \leq 30$。
6. （$8$ 分）$N \leq 400$。
7. （$20$ 分）$N \leq 1\,800$。
8. （$13$ 分）无附加限制。

---

样例解释 1

在难度 $1$ 的防御战中，可以按下述方式行动，取得评价值 $4$，无法取得评价值 $3$ 或以下。

时刻       事件
$0$        怪兽 $1$（HP $9$）出现。
$0$-$8$    对怪兽 $1$ 攻击 $8$ 次，HP 从 $9$ 减至 $1$。
$8$        怪兽 $2$（HP $5$）出现。
$8$-$9$    对怪兽 $2$ 攻击 $1$ 次，HP 从 $5$ 减至 $4$。
$9$-$10$   对怪兽 $1$ 攻击 $1$ 次，HP 从 $1$ 减至 $0$。
$10$       怪兽 $1$ 被打倒。
$10$       防御战结束，评价值为 $0 \times P_1 + 4 \times P_2 = 4$。

而在难度 $2$ 的防御战中，可以如下行动，获得评价值 $26$，无法取得评价值 $25$ 或以下。

时刻       事件
$0$        怪兽 $1$（HP $18$）出现。
$0$-$8$    对怪兽 $1$ 攻击 $8$ 次，HP 从 $18$ 减至 $10$。
$8$        怪兽 $2$（HP $10$）出现。
$8$-$10$   对怪兽 $1$ 攻击 $2$ 次，HP 从 $10$ 减至 $8$。
$10$       防御战结束，评价值为 $8 \times P_1 + 10 \times P_2 = 26$。

此外，由于本输入中 $L = 2$，不能选择难度大于等于 $3$ 的防御战。

因此输出如下：

• 对于第 $1$ 个基准值 $M_1 = 0$，任何难度都无法完成任务，第 $1$ 行输出 0。
• 对于第 $2$ 个基准值 $M_2 = 20$，最大可以完成难度 $1$ 的防御战，第 $2$ 行输出 $1$。
• 对于第 $3$ 个基准值 $M_3 = 40$，最大可以完成难度 $2$ 的防御战，第 $3$ 行输出 $2$。

该输入符合小子任务 $3, 4, 5, 6, 7, 8$ 的约束。

---

样例解释 2

该输入符合所有小子任务的约束。

---

样例解释 3

该输入符合小子任务 $2, 3, 4, 5, 6, 7, 8$ 的约束。

---

样例解释 4

该输入符合小子任务 $5, 6, 7, 8$ 的约束。

---

样例解释 5

该输入符合小子任务 $5, 6, 7, 8$ 的约束。

数据范围与限制

• $1 \leq N \leq 6\,000$。
• $1 \leq L \leq 10\,000\,000$。
• $1 \leq T \leq 10^{18}$。
• $0 \leq S_i < T$（$1 \leq i \leq N$）。
• $1 \leq H_i$（$1 \leq i \leq N$）。
• $1 \leq P_i$（$1 \leq i \leq N$）。
• $H_1 P_1 + H_2 P_2 + \cdots + H_N P_N \leq 10^{11}$。
• $1 \leq Q \leq 1\,000\,000$。
• $0 \leq M_j \leq 10^{18}$（$1 \leq j \leq Q$）。
• $M_1 < M_2 < \cdots < M_Q$。
• 输入的所有数均为整数。

由 ChatGPT 5 翻译