CF1657D For Gamers. By Gamers.

Monocarp 正在玩一款策略游戏。在游戏中，他需要招募一支小队来对抗怪物。在每场战斗前，Monocarp 有 $C$ 枚金币可用于招募小队成员。 每场战斗开始前，他的小队是空的。Monocarp 可以选择一种单位类型，并且招募该类型的单位数量不能超过他用 $C$ 枚金币所能招募的最大数量。 共有 $n$ 种单位类型。每种单位有三个参数： - $c_i$ —— 招募第 $i$ 种单位一个所需的金币数； - $d_i$ —— 第 $i$ 种单位每秒造成的伤害； - $h_i$ —— 第 $i$ 种单位的生命值。 Monocarp 需要面对 $m$ 个怪物。每个怪物有两个参数： - $D_j$ —— 第 $j$ 个怪物每秒造成的伤害； - $H_j$ —— 第 $j$ 个怪物的生命值。 Monocarp 在第 $j$ 场战斗只需对抗第 $j$ 个怪物。他希望所有招募的单位都能存活下来。Monocarp 的小队和怪物会持续（不是每秒一次）且同时攻击。因此，只有当 Monocarp 的小队击杀怪物的速度严格快于怪物击杀他任意一个单位的速度时，Monocarp 才能获胜。比较时间时不进行四舍五入。 对于每个怪物，Monocarp 想知道击杀该怪物所需花费的最少金币数。如果所需金币数大于 $C$，则认为无法击杀该怪物。

第一行包含两个整数 $n$ 和 $C$（$1 \le n \le 3 \cdot 10^5$；$1 \le C \le 10^6$）——单位类型数和每场战斗前拥有的金币数。 接下来 $n$ 行，每行包含三个整数 $c_i, d_i, h_i$（$1 \le c_i \le C$；$1 \le d_i, h_i \le 10^6$）。 接下来一行包含一个整数 $m$（$1 \le m \le 3 \cdot 10^5$）——怪物数量。 接下来 $m$ 行，每行包含两个整数 $D_j$ 和 $H_j$（$1 \le D_j \le 10^6$；$1 \le H_j \le 10^{12}$）。

输出 $m$ 个整数。对于每个怪物，输出击杀该怪物所需的最少金币数。如果所需金币数大于 $C$，则输出 $-1$。

以第一个样例的第一个怪物为例。 Monocarp 不能只招募一个第一种类型的单位，因为他和怪物都需要 $0.75$ 秒才能击杀对方。他可以招募两个该类型的单位，花费 $6$ 枚金币，在 $0.375$ 秒内击杀怪物。 Monocarp 可以只招募一个第二种类型的单位，因为他击杀怪物只需 $0.6$ 秒，而怪物击杀他需 $0.625$ 秒。单位更快。因此，$5$ 枚金币足够。 Monocarp 至少需要招募三个第三种类型的单位才能击杀第一个怪物，这将花费 $30$ 枚金币。 如果选择第二种单位类型并招募一个单位，Monocarp 花费的金币最少。 由 ChatGPT 4.1 翻译