A. 秘源机兵统御械 - 疾攻
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

在《Genshin Impart》的新版本中，两名高人气冰系角色——主 C「柯丝克」与辅助「可爱菲」迎来了复刻。两人在技能机制上有着绝佳的相性。

然而，近日柯丝克因过度沉迷少女乐队，意外患上了"人格分裂"。这导致她的战斗方式发生了特殊的变化，需要依靠可爱菲的增伤辅助来将队伍爆发提升到极致。

柯丝克一共分裂出了 $$$n$$$ 个人格，每个人格都拥有一个特定的技能。由于战斗设定的限制，柯丝克只能严格按照 $$$1, 2, \dots, n$$$ 的顺序依次切换人格，且每个人格在整场战斗中只能释放一次技能。

对于第 $$$i$$$ 个人格，其技能机制如下：

  • 持续输出期：技能释放后，每秒造成 $$$a_i$$$ 点基础伤害，持续 $$$t_i$$$ 秒。
  • 技能冷却期：输出期结束后，柯丝克将立即进入持续 $$$g_i$$$ 秒的冷却时间。
注意：在某个人格的持续输出期和技能冷却期内，柯丝克无法切换到下一个人格释放技能。

队伍中的辅助角色「可爱菲」可以释放最多 $$$m$$$ 次强度增幅技能。该技能的机制如下：

  • 增伤效果：每次增幅会提供固定持续 $$$L$$$ 秒的增伤状态。在增伤状态下，若柯丝克原本产生的秒伤为 $$$dam$$$，则实际造成的伤害将提升为 $$$dam \times (1 + P)$$$。
  • 释放限制：可爱菲的增幅技能不可重叠（即同一时间只能存在一个增幅状态），且每次增幅的开始释放时间必须落在柯丝克当前人格的技能冷却期（即 $$$g_i$$$ 的阶段）内。
  • 技能后摇：可爱菲释放增幅技能后，会立刻进入持续 $$$T$$$ 秒的技能后摇。在此期间，玩家处于"僵直"状态，无法进行任何操作（包括切换柯丝克的人格）。这意味着，如果后摇未结束而柯丝克的 $$$g_i$$$ 已经结束，柯丝克也必须等待后摇结束后才能切换至下一个人格触发技能。

定义队伍的整场战斗时间为：从第 $$$1$$$ 个人格释放技能开始，直到第 $$$n$$$ 个人格的技能流程及可能存在的后摇完全结束为止的总时长。

定义整场战斗的 $$$\text{DPS}$$$（Damage Per Second，秒伤）为： $$$$$$ \text{DPS} = \frac{\text{队伍造成的总伤害}}{\text{队伍消耗的总时间}} $$$$$$

请你制定一套合理的增幅技能释放策略（包括在哪些人格的冷却期释放、在冷却期的哪个具体时间点释放），使得整场战斗的 $$$\text{DPS}$$$ 达到最大。

求出该队伍能够达到的最大可能 DPS。

Input

第一行包含四个正整数 $$$n,m,L,T$$$ 。

第二行包含一个小数，表示 $$$P$$$ 。

第三到 $$$n+2$$$ 行，每行包含三个正整数 $$$a_i,t_i,g_i$$$。

Output

输出最大的可能的 DPS(Damage per second)，也就是该队伍平均每秒造成的伤害，四舍五入到整数。

Example
Input
3 1 5 2
0.5
10 2 3
20 4 2
30 3 1
Output
16
Note

$$$ 1 \le n,m \le 1 \times 10^4$$$

$$$ 1 \le a_i,t_i,g_i,L,T \le 10^9$$$

$$$ 0 \lt P \le 100$$$

保证输入的技能增益倍率 P 最多只包含两位有效小数。

保证游戏进行的最大总时间与造成的最大总伤害，在最坏情况下的理论极限乘积不会超过 128 位有符号整数（__int128）的上限。

数据生成规则说明本题的测试数据均由官方生成器按照以下随机规则生成。令 rand(L, R) 表示在 $$$[L, R]$$$ 范围内均匀随机生成一个整数，rand_float(L, R) 表示均匀随机生成一个浮点数。给定基本参数 $$$n$$$ (人格数量), $$$m_{type}$$$ (次数限制类型), $$$mode$$$ (数据特性模式) 以及 $$$max\_val$$$ (数值量级上限，最高可达 $$$10^9$$$)。生成逻辑如下：


if m_type == 0: m = 0
else if m_type == 1: m = 1
else if m_type == 2: m = max(1, n / 2)
else if m_type == 3: m = n
else: m = rand(1, n)

if mode == 4:
    T = rand(1, 1000)
    L = rand(max_val / 2, max_val)
else:
    T = rand(1, max_val / 10)
    if rand(0, 1) == 0: L = rand(T, T * 5)
    else:               L = rand(1, max_val / 5)

P = rand_float(0.01, 100.0) 

if mode == 3:
    if rand(0, 9) == 0: a_i = rand(max_val / 2, max_val)
    else:               a_i = rand(1, 10000)
else:
    a_i = rand(1, max_val)

if mode == 3:
    if a_i > max_val / 2: t_i = rand(1, 100)
    else:                 t_i = rand(1, max_val / 1000)
else:
    t_i = rand(1, max_val / 100)

if mode == 1:
    g_i = rand(T, max(T + 1000, max_val / 100))
else if mode == 2:
    if T > 1: g_i = rand(1, T - 1)
    else:     g_i = 1
else:
    g_i = rand(1, max_val / 100)