← 返回题目列表

Codeforces · 1657/D

D. 对于游戏玩家。由游戏玩家提供。

中文机器翻译题面 查看原题

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 想知道杀死该怪物所需花费的最少金币。如果这个金额大于$$$C$$$,则报告不可能杀死该怪物。

输入

第一行包含两个整数 $$$n$$$ 和 $$$C$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le C \le 10^6$$$) – 单位类型的数量以及 Monocarp 在每场战斗之前拥有的金币数量。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含三个整数 $$$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$$$) — Monocarp 必须面对的怪物数量。

接下来的 $$$m$$$ 行的第 $$$j$$$ 行包含两个整数 $$$D_j$$$ 和 $$$H_j$$$ ($$$1 \le D_j \le 10^6$$$; $$$1 \le H_j \le 10^{12}$$$)。

输出

打印 $$$m$$$ 整数。对于每个怪物,打印 Monocarp 杀死该怪物所需花费的最小硬币数量。如果该金额大于 $$$C$$$,则打印 $$$-1$$$。

示例

输入 #1

3 10
3 4 6
5 5 5
10 3 4
3
8 3
5 4
10 15

输出 #1

5 3 -1

输入 #2

5 15
14 10 3
9 2 2
10 4 3
7 3 5
4 3 1
6
11 2
1 1
4 7
2 1
1 14
3 3

输出 #2

14 4 14 4 7 7

输入 #3

5 13
13 1 9
6 4 5
12 18 4
9 13 2
5 4 5
2
16 3
6 2

输出 #3

12 5

注意

考虑第一个示例的第一个怪物。

Monocarp 无法招募第一种类型的单位,因为他和怪物需要 $$$0.75$$$ 秒才能杀死对方。他可以花费 $$$6$$$ 硬币招募两个单位,并在 $$$0.375$$$ 秒内杀死怪物。

Monocarp可以招募一个第二类型的单位,因为他在$$$0.6$$$秒内杀死了怪物,而怪物在$$$0.625$$$秒内杀死了他。单位速度更快。因此,$$$5$$$硬币就足够了。

Monocarp 需要至少三个第三种单位才能杀死第一个怪物,这将花费 $$$30$$$ 金币。

如果 Monocarp 选择第二种类型的单位并招募一个该类型的单位,他将花费最少的金币。