AT_joigsp2025_h.勇者ビ太郎 3 (Bitaro the Brave 3)

勇者比太郎准备挑战一项保卫村庄免受怪物侵袭的防卫战任务。防卫战的难度用一个大于等于 $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$ 到达时，防卫战结束，接着计算防卫战的评价值。

• 用 $h_i$ 表示时刻 $T$ 后第 $i$ 只怪物（$1 \leq i \leq N$）剩余的 HP，则评价值为 $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.（$5$ 分）$N \leq 30$，$Q = 1$，$M_1 = 0$，$L = 1$。
2.（$10$ 分）$N \leq 30$，$Q = 1$，$M_1 = 0$。
3.（$14$ 分）$N \leq 30$，$Q \leq 3$。
4.（$10$ 分）$Q \leq 3$。
5.（$33$ 分）$N \leq 30$。
6.（$7$ 分）$N \leq 400$。
7.（$16$ 分）$N \leq 1\,800$。
8.（$5$ 分）无额外限制。

---

样例说明 1

当难度为 $1$ 时，可以按以下方式操作，使评价值为 $4$，无法达成 $3$ 或以下：

时刻     事件
0        怪物1（HP9）出现。
0-8      攻击怪物1，总共8次；其HP由9降到1。
8        怪物2（HP5）出现。
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（HP18）出现。
0-8      攻击怪物1，总共8次；其HP由18降到10。
8        怪物2（HP10）出现。
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 翻译