← 返回题目列表

Codeforces · 912/C

C. 佩伦,大招!

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

许多学生高效地度过了寒假。弗拉德在这方面已经取得了很大进步!已经三天了,在沙拉和橘子(新年庆祝活动的剩菜)的刺激下,他一直在他最喜欢的 MOBA 游戏中校准自己的评分,扮演一个名叫 Perun 的英雄。

佩伦有一个名为“雷霆之怒”的终极能力。在其激活的瞬间,地图上的每个敌人(总共 n 个)会一次性损失 $$damage$$ 生命值。它还有一个限制:只有当时刻为整数时才能激活。杀死敌人的初始赏金是$$bounty$$。此外,它每秒增加$$increase$$。正式来说,如果在某个时刻 t 该能力被激活并且第 i 个敌人因此被杀死(即他的生命值降至零或更低),弗拉德将获得 $$ 赏金 + t \cdot 增加 $$ 单位的黄金。

每个敌人都会受到伤害并得到治疗。有多种方法可以做到这一点,但弗拉德对细节不感兴趣。对于他所知道的 n 个敌人中的每一个:

- $${\mathrm {max}}_{\mathrm{health}}$$ — 第 i 个敌人的最大生命值;
- $$\texttt{start\_health}$$ — 敌人的初始生命值(第 0 秒);
- $$r_{\mathrm{regen}}$$ — 第 i 个敌人每秒可以恢复的生命值。

Vlad 还知道以下健康状况更新:

- $${ \mathrm { t i me } } _ { j }$$ — 健康状况更新的时间;
- $$enemy_j$$ — 生命值已更新的敌人;
- $$health_j$$ — 更新了敌人 j 的生命值。

显然,Vlad 希望最大化他的利润。如果有必要的话,他甚至可以等上好几年,才能在合适的时机发动自己的能力。帮助他确定从 0(含)到 + ∞ 的精确秒数(注意它必须是整数),以便单次激活该能力将给 Vlad 带来最大可能的黄金数量,并打印这个数量。

输入

在第一行中,给出了两个整数(用空格分隔)— n 和 m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105)。

第二行有三个整数:$$bounty$$、$$increase$$ 和 $$damage$$ ($${ 1 \leq bo u n t y, d a m a g e \leq 1 0 ^ { 9 } }$$, $$0 \leq raise \leq 10^4$$)。

以下 n 行中的每一行都有三个整数 - $${\mathrm {max}}_{\mathrm{health}}$$, $$\texttt{start\_health}$$, $$r_{\mathrm{regen}}$$ ($$1 \leq start\_health_i \leq max\_health_i \leq 10^9$$, $$0 \leq regen_i \leq max_health_i$$)。

接下来的 m 行每行包含三个整数 - $${ \mathrm { t i me } } _ { j }$$, $$enemy_j$$, $$health_j$$ ($${ 1 \leq t i m e _ { j } \leq 1 0 ^ { 9 } }$$, $${ 1 \leq e n e m y _ { j } \leq n }$$,$${ 1 \leq h e a l t h _ { j } \leq m a x _ { - he a l t h _ { en e m y _ { j } } } }$$)。保证每个敌人每秒不超过一次壁炉变化:更正式地说,对于每个 a, b,使得 1 ≤ a, b ≤ m, a ≠ b 成立,如果 $$time_{a} = time_{b}$$,则 $$enemy_{a} \neq heaven_{b}$$。

输出

输出单个整数——如果 Vlad 仅应用一次“雷霆之怒”,他可以获得的最大金币数量;如果该数量可以无限大,则输出 -1。

示例

输入 #1

3 2
1000 10 50
70 5 5
90 70 1
110 20 2
20 2 10
30 3 10

输出 #1

3000

输入 #2

1 1
500 50 1000
750 750 20
10 1 300

输出 #2

-1

注意

在图片上,您可以看到示例案例中每个敌人的生命值与时间的关系。

弗拉德可以杀死一名敌人的时间段用黄色标记。

弗拉德可以杀死两个敌人的时间段用紫色标记。

在第一个示例案例中,Vlad 可以在第 50 秒激活该能力:敌人 2 和 3 将死亡,因为他们分别有 40 和 50 点生命值。弗拉德将获得 2·(1000 + 50·10) = 3000 金币。

在第二个示例案例中,敌人 1 的最大生命值小于该能力造成的伤害。因此,敌人随时都有可能被杀死。随着赏金随着时间的推移增加 50,最大可能的金币数量是无限的。