For Gamers. By Gamers.

题意翻译

Monocarp 要逐个击败 $m$ 只怪物，第 $i$ 只怪物的血量为 $H_i$，攻击力为 $D_i$。 Monocarp 没有战斗力，但他有 $C$ 个金币 ，他可以用这些金币招募一个小队与怪物战斗 Monocarp 在与每一只怪物战斗前都有 $C$ 个金币用来招募战士 Monocarp 可以招募的战士有 $n$ 种类型，第 $i$ 种类型的每个战士有 $h_i$ 的血量，$d_i$ 的伤害和 $c_i$ 的费用 Monocarp 深知团队和谐的重要性，所以他招募的战士只能是同种类型的，并且他希望每一个战士都不会死 Monocarp 招募的小队能战胜怪物当且仅当他们杀死怪物的时间比怪物杀死小队的一个战士的时间短 Monocarp 知道如果一个战士攻击力为 $d$，一个怪物血量为 $H$，那么战士击败怪物需要 $\frac{H}{d}$ 的时间（不舍入），怪物击败战士同理 Monocarp 想知道他杀死每个怪物至少要多少金币，如果这个数字大于 $C$，请输出 $-1$ $n, m \le 3 \times 10^5$ $C, h_i, d_i, D_i \le 1 \times 10^6, H_i \le 1 \times 10^{12}, c_i \le C$

题目描述

Monocarp is playing a strategy game. In the game, he recruits a squad to fight monsters. Before each battle, Monocarp has $ C $ coins to spend on his squad. Before each battle starts, his squad is empty. Monocarp chooses one type of units and recruits no more units of that type than he can recruit with $ C $ coins. There are $ n $ types of units. Every unit type has three parameters: - $ c_i $ — the cost of recruiting one unit of the $ i $ -th type; - $ d_i $ — the damage that one unit of the $ i $ -th type deals in a second; - $ h_i $ — the amount of health of one unit of the $ i $ -th type. Monocarp has to face $ m $ monsters. Every monster has two parameters: - $ D_j $ — the damage that the $ j $ -th monster deals in a second; - $ H_j $ — the amount of health the $ j $ -th monster has. Monocarp has to fight only the $ j $ -th monster during the $ j $ -th battle. He wants all his recruited units to stay alive. Both Monocarp's squad and the monster attack continuously (not once per second) and at the same time. Thus, Monocarp wins the battle if and only if his squad kills the monster strictly faster than the monster kills one of his units. The time is compared with no rounding. For each monster, Monocarp wants to know the minimum amount of coins he has to spend to kill that monster. If this amount is greater than $ C $ , then report that it's impossible to kill that monster.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ C $ ( $ 1 \le n \le 3 \cdot 10^5 $ ; $ 1 \le C \le 10^6 $ ) — the number of types of units and the amount of coins Monocarp has before each battle. The $ i $ -th of the next $ n $ lines contains three integers $ c_i, d_i $ and $ h_i $ ( $ 1 \le c_i \le C $ ; $ 1 \le d_i, h_i \le 10^6 $ ). The next line contains a single integer $ m $ ( $ 1 \le m \le 3 \cdot 10^5 $ ) — the number of monsters that Monocarp has to face. The $ j $ -th of the next $ m $ lines contains two integers $ D_j $ and $ H_j $ ( $ 1 \le D_j \le 10^6 $ ; $ 1 \le H_j \le 10^{12} $ ).

输出格式

Print $ m $ integers. For each monster, print the minimum amount of coins Monocarp has to spend to kill that monster. If this amount is greater than $ C $ , then print $ -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

说明

Consider the first monster of the first example. Monocarp can't recruit one unit of the first type, because it will take both him and the monster $ 0.75 $ seconds to kill each other. He can recruit two units for the cost of $ 6 $ coins and kill the monster in $ 0.375 $ second. Monocarp can recruit one unit of the second type, because he kills the monster in $ 0.6 $ seconds, and the monster kills him in $ 0.625 $ seconds. The unit is faster. Thus, $ 5 $ coins is enough. Monocarp will need at least three units of the third type to kill the first monster, that will cost $ 30 $ coins. Monocarp will spend the least coins if he chooses the second type of units and recruits one unit of that type.