English · Original
Chinese · Translation
Formal · Original
A lot of students spend their winter holidays productively. Vlad has advanced very well in doing so! For three days already, fueled by salads and tangerines — the leftovers from New Year celebration — he has been calibrating his rating in his favorite MOBA game, playing as a hero named Perun.
Perun has an ultimate ability called "Thunderwrath". At the instant of its activation, each enemy on the map (_n_ of them in total) loses health points as a single-time effect. It also has a restriction: it can only activated when the moment of time is an **integer**. The initial bounty for killing an enemy is . Additionally, it increases by each second. Formally, if at some second _t_ the ability is activated and the _i_\-th enemy is killed as a result (i.e. his health drops to zero or lower), Vlad earns units of gold.
Every enemy can receive damage, as well as be healed. There are multiple ways of doing so, but Vlad is not interested in details. For each of _n_ enemies he knows:
* — maximum number of health points for the _i_\-th enemy;
* — initial health of the enemy (on the 0\-th second);
* — the amount of health the _i_\-th enemy can regenerate per second.
There also _m_ health updates Vlad knows about:
* — time when the health was updated;
* — the enemy whose health was updated;
* — updated health points for _enemy__j_.
Obviously, Vlad wants to maximize his profit. If it's necessary, he could even wait for years to activate his ability at the right second. Help him determine the exact second (note that it must be **an integer**) from 0 (inclusively) to + ∞ so that a single activation of the ability would yield Vlad the maximum possible amount of gold, and print this amount.
## Input
In the first line, two integers are given (separated by spaces) — _n_ and _m_ (1 ≤ _n_ ≤ 105, 0 ≤ _m_ ≤ 105).
In the second line, there are three integers: , and (, ).
Each of the following _n_ lines has three integers — , , (, ).
The next _m_ lines contain three integers each — , , (, , ). It is guaranteed that there is no more than one hearth change per second for each enemy: more formally, for each _a_, _b_ so that 1 ≤ _a_, _b_ ≤ _m_, _a_ ≠ _b_ holds that if , then .
## Output
Output the single integer — the maximum amount of gold Vlad can obtain if he applies "Thunderwrath" exactly once, or _\-1_ if this amount can be **infinitely** large.
[samples]
## Note
On the pictures you can see health points of each enemy versus time in sample cases.
_Periods when Vlad can kill one enemy are marked with yellow color._
_Periods when Vlad can kill two enemies are marked with purple color._
<center></center>In the first sample case, Vlad can activate the ability at the 50\-th second: the enemies 2 and 3 will die since they would have 40 and 50 health points correspondingly. Vlad will earn 2·(1000 + 50·10) = 3000 gold.
<center></center>In the second sample case, the maximum amount of health for the enemy 1 is less than the damage dealt by the ability. Hence, the enemy could be killed anytime. As the bounty increases by 50 over the time, the maximum possible amount of gold is infinite.
许多学生在寒假期间都过得非常充实。弗拉德在这方面进步得非常快！他已经连续三天，靠着沙拉和柑橘——新年庆祝后剩下的食物——打磨他在最爱的MOBA游戏中扮演英雄“佩伦”时的评分。
佩伦有一个终极技能，名为“雷怒”。在激活的瞬间，地图上的每个敌人都会因一次性效果损失 $ d $ 点生命值。该技能有一个限制：只能在时间点为 *整数* 时激活。击杀敌人的初始赏金为 $ b $。此外，赏金每秒增加 $ p $。形式上，如果在第 $ t $ 秒激活该技能，且第 $ i $ 个敌人的生命值因此降至零或更低，则弗拉德将获得 $ b + p \cdot t $ 单位金币。
每个敌人都可以受到伤害，也可以被治疗。虽然有多种方式实现这一点，但弗拉德并不关心细节。对于每个敌人都知道：
此外，弗拉德还知道 $ m $ 次生命值更新：
显然，弗拉德希望最大化他的收益。如果有必要，他甚至可以等待数年，直到在正确的整数时刻激活技能。请帮他确定确切的时刻（注意必须是 *整数*），该时刻在 $ 0 $（含）到 $ +\infty $ 之间，使得单次激活技能能获得尽可能多的金币，并输出该最大金额。
第一行包含两个整数（用空格分隔）—— $ n $ 和 $ m $（$ 1 \leq n \leq 10^5 $，$ 0 \leq m \leq 10^5 $）。
第二行包含三个整数：$ b $、$ p $ 和 $ d $（$ 1 \leq b, p, d \leq 10^9 $）。
接下来的 $ n $ 行每行包含三个整数——$ h_i $、$ a_i $、$ r_i $（$ 1 \leq h_i, a_i, r_i \leq 10^9 $）。
接下来的 $ m $ 行每行包含三个整数——$ t_i $、$ a_i $、$ r_i $（$ 1 \leq t_i \leq 10^9 $，$ 1 \leq a_i, r_i \leq 10^9 $）。保证对于每个敌人，每秒最多发生一次生命值变化：更正式地说，对于任意 $ a, b $ 满足 $ 1 \leq a, b \leq m $ 且 $ a \neq b $，若两个更新作用于同一敌人，则它们的时间不同。
输出一个整数——如果弗拉德恰好使用一次“雷怒”，他能获得的最大金币数；如果该金额可以是 *无限大*，则输出 _-1_。
在图中可以看到每个敌人的生命值随时间变化的情况。
_黄色区域表示弗拉德可以击杀一个敌人的时段。_
_紫色区域表示弗拉德可以击杀两个敌人的时段。_
在第一个样例中，弗拉德可以在第 $ 50 $ 秒激活技能：敌人 $ 2 $ 和 $ 3 $ 将死亡，因为它们此时的生命值分别为 $ 40 $ 和 $ 50 $。弗拉德将获得 $ 2 \cdot (1000 + 50 \cdot 10) = 3000 $ 金币。
在第二个样例中，敌人 $ 1 $ 的最大生命值小于技能造成的伤害。因此，该敌人可以在任意时刻被击杀。由于赏金随时间每秒增加 $ 50 $，最大可能金币数是无限的。
## Input
在第一行，两个整数是给定的（用空格分隔）—— $ n $ 和 $ m $（$ 1 \leq n \leq 10^5 $，$ 0 \leq m \leq 10^5 $）。在第二行，有三个整数：$ b $、$ p $ 和 $ d $（$ 1 \leq b, p, d \leq 10^9 $）。接下来的 $ n $ 行每行有三个整数——$ h_i $、$ a_i $、$ r_i $（$ 1 \leq h_i, a_i, r_i \leq 10^9 $）。接下来的 $ m $ 行每行包含三个整数——$ t_i $、$ a_i $、$ r_i $（$ 1 \leq t_i \leq 10^9 $，$ 1 \leq a_i, r_i \leq 10^9 $）。保证对于每个敌人，每秒最多发生一次生命值变化：更正式地说，对于任意 $ a, b $ 满足 $ 1 \leq a, b \leq m $ 且 $ a \neq b $，若两个更新作用于同一敌人，则它们的时间不同。
## Output
输出一个整数——如果弗拉德恰好使用一次“雷怒”，他能获得的最大金币数；如果该金额可以是 *无限大*，则输出 _-1_。
[samples]
## Note
在图中可以看到每个敌人的生命值随时间变化的情况。_黄色区域表示弗拉德可以击杀一个敌人的时段。_ _紫色区域表示弗拉德可以击杀两个敌人的时段。_ 在第一个样例中，弗拉德可以在第 $ 50 $ 秒激活技能：敌人 $ 2 $ 和 $ 3 $ 将死亡，因为它们此时的生命值分别为 $ 40 $ 和 $ 50 $。弗拉德将获得 $ 2 \cdot (1000 + 50 \cdot 10) = 3000 $ 金币。 在第二个样例中，敌人 $ 1 $ 的最大生命值小于技能造成的伤害。因此，该敌人可以在任意时刻被击杀。由于赏金随时间每秒增加 $ 50 $，最大可能金币数是无限的。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of enemies, $ m \in \mathbb{Z}_{\geq 0} $ the number of health updates.
Let $ D \in \mathbb{Z}^+ $ be the fixed damage per ability activation.
Let $ b \in \mathbb{Z}^+ $ be the base bounty per enemy.
Let $ r \in \mathbb{Z}^+ $ be the rate of bounty increase per second.
For each enemy $ i \in \{1, \dots, n\} $:
- Let $ h_i \in \mathbb{Z}^+ $ be the initial health.
- Let $ p_i \in \mathbb{Z} $ be the health change per second (positive = healing, negative = damage).
- Let $ H_i(t) = h_i + p_i \cdot t $ be the health of enemy $ i $ at integer time $ t \geq 0 $.
Let $ U = \{ (t_u, i_u, \Delta_u) \mid u \in \{1, \dots, m\} \} $ be the set of health updates, where at time $ t_u \in \mathbb{Z}_{\geq 0} $, enemy $ i_u \in \{1, \dots, n\} $ has its health changed by $ \Delta_u \in \mathbb{Z} $, modifying $ H_{i_u}(t) $ for $ t \geq t_u $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $, $ 0 \leq m \leq 10^5 $
2. $ 1 \leq D, b, r \leq 10^9 $
3. $ 1 \leq h_i \leq 10^9 $, $ |p_i| \leq 10^4 $
4. For each update: $ 0 \leq t_u \leq 10^9 $, $ 1 \leq i_u \leq n $, $ |\Delta_u| \leq 10^9 $
5. No two updates occur at the same time for the same enemy.
**Objective**
For each integer $ t \geq 0 $, define the set of killed enemies:
$$ K(t) = \{ i \in \{1, \dots, n\} \mid H_i(t) \leq D \} $$
The gold earned at time $ t $ is:
$$ G(t) = |K(t)| \cdot (b + r \cdot t) $$
Find:
$$ \max_{t \in \mathbb{Z}_{\geq 0}} G(t) $$
If $ \sup_{t \in \mathbb{Z}_{\geq 0}} G(t) = +\infty $, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "C. Perun, Ult!",
"description": {
"content": "A lot of students spend their winter holidays productively. Vlad has advanced very well in doing so! For three days already, fueled by salads and tangerines — the leftovers from New Year celebration —",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF912C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "A lot of students spend their winter holidays productively. Vlad has advanced very well in doing so! For three days already, fueled by salads and tangerines — the leftovers from New Year celebration —...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "许多学生在寒假期间都过得非常充实。弗拉德在这方面进步得非常快！他已经连续三天，靠着沙拉和柑橘——新年庆祝后剩下的食物——打磨他在最爱的MOBA游戏中扮演英雄“佩伦”时的评分。\n\n佩伦有一个终极技能，名为“雷怒”。在激活的瞬间，地图上的每个敌人都会因一次性效果损失 $ d $ 点生命值。该技能有一个限制：只能在时间点为 *整数* 时激活。击杀敌人的初始赏金为 $ b $。此外，赏金每秒增加 $ p ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of enemies, $ m \\in \\mathbb{Z}_{\\geq 0} $ the number of health updates. \nLet $ D \\in \\mathbb{Z}^+ $ be the fixed damage per ability activati...",
"is_translate": false,
"language": "Formal"
}
]
}