#212052. [JOIST 2025] 勇者比太郎 3 / Bitaro the Brave 3

本题测试点极大，评测时可能需要等待较长时间加载测试点。

比太郎在打防御战。防御战的难度用一个 的整数表示，这个值可以在任务开始时选择。在难度为 （）的防御战中，怪物的生命值会是难度 时的 倍。

防御战持续 秒，期间会有 只怪物出现。每只怪物被分配一个从 到 的唯一编号。时间 （）指战斗开始后 秒的时刻。

怪物 （）会在时间 （）出现，强度为 ，且在难度 下的生命值为 。

在防御战中，比太郎可以无限次执行以下动作：

• 选择当前在场的一只怪物并攻击它，这需要 秒的时间。怪物的生命值会减少 。一旦怪物的生命值降为 ，它将被视为被击败并不再被攻击。

当时间到达 时，防御战结束，并按以下规则计算惩罚分：

• 设 为时间 后怪物 （）的剩余生命值。惩罚分为 。

如果惩罚分小于等于任务指定的阈值 ，则比太郎成功完成任务。由于更高难度会带来更好的奖励，比太郎希望确定他能完成任务的最髙难度等级。但阈值 是未知的，因此比太郎决定针对 个候选阈值 ，分别找出能完成任务的最髙难度等级。

给定防御战的信息和候选阈值，请编写一个程序：对于每个阈值，判断任务是否可完成，并在可能的情况下找出可完成的最髙难度等级。

输出 行。在第 行（），输出当 时能完成任务的最髙难度等级。如果在任何难度下都无法完成任务，则输出 。

样例输入 1

2 2 10
0 9 2
8 5 1
3
0
20
40

样例输出 1

0
1
2

样例输入 2

3 1 100000000000
60000000000 30000000000 1
30000000000 45000000000 1
10000000000 10000000000 1
1
0

样例输出 2

0

样例输入 3

3 10000000 100000000
60000000 4 1
30000000 6 1
0 2 1
1
0

样例输出 3

7000000

样例输入 4

5 20 100
0 3 1
20 2 2
40 1 3
60 4 4
80 2 5
11
0
50
100
150
200
250
300
350
400
450
500

样例输出 4

6
8
10
12
13
15
16
18
19
20
20

子任务

样例解释

在难度为 的防守战中，可以采取以下行动来达到 的惩罚分。无法达到 或更低的惩罚分。

此外，在难度为 的防守战中，可以采取以下行动来达到 的惩罚分。无法达到 或更低的惩罚分。

此外，在此输入示例中，由于 ，无法选择难度 或更高的防御战。因此输出如下：

• 对于第一个阈值 ，无法在任何难度下完成任务，故第一行输出 。
• 对于第二个阈值 ，最多能在难度 下完成任务，故第二行输出 。
• 对于第三个阈值 ，最多能在难度 下完成任务，故第三行输出 。

该样例满足子任务 的限制。

样例解释

该样例满足所有子任务的限制。

样例解释

该样例满足子任务 的限制。

样例解释

该样例满足子任务 的限制。

数据范围

• ；
• ；
• ；
• （）；
• （）；
• （）；
• ；
• ；
• （）；
• ；
• 输入的所有值均为整数。

子任务

• ：，，，。
• ：，，。
• ：，。
• ：。
• ：。
• ：。
• ：。
• ：无额外限制。