该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你说的对，但是《原坤》是由新赛道OI自主研发的一款全新开放世界冒险游戏，考虑到游戏已经家喻户晓，所以在此省略两万字的游戏介绍。

正值五一佳节版本，游戏中推出了一名新的翔元素双手键角色 "Ikun战士"，该角色一共有三个技能：

1. 普通攻击【翔龙在天】：一共分为 $n$ 段，使用第 $i$ 段普通攻击会花费 ${t_i}$ 秒的时间，造成 ${d_i}$ 点伤害，并让角色获得 ${e_i}$ 点怒气值。只有连续使用普通攻击时才会叠加段数，第 $n$ 段普通攻击结束后或者使用了其他技能后再使用普通攻击，都会从第 $1$ 段开始重新计算。

2. 怒气爆发【翔空万里】：当怒气值达到 $E$ 时才能使用，使用后怒气值将变为 $0$。使用怒气爆发会花费 ${t_a}$ 秒的时间，造成 ${d_a}$ 点伤害，并让角色获得增益效果之后的 $m$ 次普通攻击造成的伤害翻倍。如果在增益效果结束前再次使用怒气爆发，会清除之前的增益效果并重新获得增益效果。怒气爆发使用完毕后该技能的冷却时间将变成 ${u_a}$ 秒。

3. 怒气战技【龙翔虎跃】：使用怒气战技会花费 ${t_b}$ 秒的时间，造成 ${d_b}$ 点伤害，让角色获得 ${e_b}$ 点怒气值并减少怒气爆发 $w$ 秒的冷却时间。怒气战技使用完毕后该技能的冷却时间将变成 ${u_b}$ 秒。

友情提示：每个技能的冷却时间都是独立计算的，每秒钟所有技能的冷却时间都会减少 $1$ 秒，冷却时间最少为 $0$ 秒，当技能的冷却时间大于 $0$ 秒时不能使用该技能。任意技能在使用过程中都不会被打断，每个技能在使用完毕后才能使用下一个技能。

小$W$ 作为新赛道OI的游戏策划，现在需要测试一下新角色的强度，但由于他很懒，所以他只会按照最简单的方式使用技能：可以使用技能时，优先使用怒气爆发，其次使用怒气战技，最后使用普通攻击。

初始时角色的怒气值为 $0$，怒气战技和怒气爆发的冷却时间也均为 $0$，没有增益效果也没有叠加普通攻击的段数。

现在小$W$ 想知道，如果想要造成 $s$ 点伤害，至少需要多少秒？为了历练新人，所以小$W$ 将任务分配给了新招的临时工，也就是你。

输入格式

第一行包含两个整数 $n$ 和 $s$，表示普通攻击分为 $n$ 段，总共需要造成 $s$ 点伤害。

第二行包含五个整数 $E$、$m$、${t_a}$、${d_a}$ 和 ${u_a}$，表示怒气值达到 $E$ 后才能使用怒气爆发，获得 $m$ 次普通攻击的增益，花费 ${t_a}$ 秒时间，造成 ${d_a}$ 点伤害，冷却时间变成 ${u_a}$ 秒。

第三行包含五个整数 $w$、${e_b}$、${t_b}$、${d_b}$、${u_b}$，表示怒气战技减少怒气爆发 $w$ 秒冷却，获得 ${e_b}$ 点怒气值，花费 ${t_b}$ 秒时间，造成 ${d_b}$ 点伤害，冷却时间变成 ${u_b}$ 秒。

接下来 $n$ 行每行包含三个整数 ${t_i}$、${d_i}$ 和 ${e_i}$，按顺序描述每一段普通攻击，花费 ${t_i}$ 秒时间，造成 ${d_i}$ 点伤害，获得 ${e_i}$ 点怒气值。

输出格式

输出一个整数，表示要造成 $s$ 点伤害需要的最少时间。

样例

2 22
1 0 1 1 1
3 0 3 4 7
2 3 0
1 2 0

16

2 26
6 2 1 1 10
3 3 1 2 5
2 3 4
1 2 5

13

见下发大样例 ikun3.in

见下发大样例 ikun3.out

见下发大样例 ikun4.in

见下发大样例 ikun4.out

见下发大样例 ikun5.in

见下发大样例 ikun5.out

样例解释

样例 1 解释

由于所有技能获得的怒气值均为 $0$，所以一直无法使用怒气爆发。

1. 首先使用怒气战技，花费 $3$ 秒，造成 $4$ 点伤害，该技能冷却时间变成 $7$ 秒。
2. 然后依次使用普通攻击第 $1, 2, 1, 2, 1$ 段，共花费 $8$ 秒，造成 $13$ 点伤害。
3. 此时怒气战技的冷却时间为 $0$ 秒，再次释放怒气战技，花费 $3$ 秒，造成 $4$ 点伤害。
4. 最后使用普通攻击第 $1$ 段，花费 $2$ 秒，造成 $3$ 点伤害。

此时总伤害为 $24$，达到目标，共花费 $16$ 秒。

样例 2 解释

1. 首先使用怒气战技，花费 $1$ 秒，造成 $2$ 点伤害，获得 $3$ 点怒气值，该技能冷却时间变成 $5$ 秒。
2. 然后使用普通攻击第 $1$ 段，花费 $2$ 秒，造成 $3$ 点伤害，获得 $4$ 点怒气值。
3. 此时怒气值达到 $7$，使用怒气爆发，怒气值变成 $0$，花费 $1$ 秒，造成 $1$ 点伤害，获得 $2$ 次普通攻击的增益，该技能冷却时间变成 $10$ 秒。
4. 然后使用增益普通攻击第 $1$ 段，花费 $2$ 秒，造成 $6$ 点伤害，获得 $4$ 点怒气值。
5. 此时怒气战技的冷却时间为 $0$ 秒，再次释放怒气战技，花费 $1$ 秒，造成 $2$ 点伤害，获得 $3$ 点怒气值，并减少了怒气爆发 $3$ 秒的冷却。
6. 然后使用增益普通攻击第 $1$ 段，普通攻击第 $2, 1$ 段，共花费 $5$ 秒，造成 $11$ 点伤害，获得 $13$ 点怒气值。
7. 此时怒气战技和怒气爆发的冷却时间均为 $0$，怒气值达到 $20$，优先使用怒气爆发，花费 $1$ 秒，造成 $1$ 点伤害。

此时总伤害为 $26$，达到目标，共花费 $13$ 秒。

大样例数据

Ikun战士大样例

数据范围

对于所有测试点，满足：

• 关于普通攻击段数、增益效果与伤害总量：$1 \leq n \leq 5$，$0 \leq m \leq 10$，$1 \leq s \leq 10^{18}$；
• 关于技能的耗时、伤害与怒气：$1 \leq {t_a}, {t_b}, {t_i}, {d_a}, {d_b}, {d_i} \leq 3$，$0 \leq {e_i}, {e_b}, w \leq 3$；
• 关于技能的冷却时间与怒气条件：$0 \leq {u_a} \leq 30$，$0 \leq {u_b} \leq 15$，$1 \leq E \leq 80$。

子任务及其特殊属性如下：

• 子任务 $1$ 占 $10\%$的分数，满足 ${u_b} = {e_b} = 0$，表示怒气战技的冷却与获得怒气均为 $0$ 。
• 子任务 $2$ 占 $20\%$的分数，满足 ${e_i} = {e_b} = 0$，${t_i} = {t_a} = {t_b} = 1$，$s \leq 10^6$，表示所有技能均不会获得怒气且耗时为$1$，总伤害较少。
• 子任务 $3$ 占 $20\%$的分数，满足 ${t_i} = {t_a} = {t_b} = 1$，$s \leq 10^6$，表示所有技能均耗时为$1$，总伤害较少。
• 子任务 $4$ 占 $30\%$的分数，满足 $s \leq 10^6$，表示总伤害较少。
• 子任务 $5$ 占 $20\%$的分数，没有特殊属性。