许多学生高效地度过了寒假。弗拉德在这方面已经取得了很大进步!已经三天了,在沙拉和橘子(新年庆祝活动的剩菜)的刺激下,他一直在他最喜欢的 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,最大可能的金币数量是无限的。