菁英战斗兵¶

参考时间限制：1.0 秒（参考环境：评测环境与性能；仅供预估）
实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
内存限制：128 MB

背景故事¶

鲍里斯和铁狗再次突入敌军重围。铁狗可以潜入指挥部，让一个兵种的全部单位瘫痪退出战斗，或者为鲍里斯增加生命值；剩下的工作则交给他的 AKM。

侦察机发回的情报里，敌军既有战斗单位，也有无法造成伤害的生产单位，甚至还有攻击反而会给鲍里斯回血的奇怪单位。任务要求一个不留，但可以讲究处理顺序。毕竟，“敌人的火力支援”偶尔也能按字面理解。

请计算鲍里斯完成任务后最多能剩下多少生命值。

有 \(K\) 种敌军单位，共 \(N\) 个。兵种 \(i\) 的每个单位初始生命值为 \(h_i\) ，攻击力为 \(a_i\) ；\(a_i<0\) 表示它的攻击为鲍里斯回复生命。鲍里斯初始生命值为 \(H\)（Health），每次攻击造成 \(A\)（Attack）点伤害。

战斗开始前，铁狗执行以下两项中的一项，且仅执行一次：

只要还有敌人，每回合必须执行：

若鲍里斯开始攻击一个 \(a_i>0\) 的兵种，在该兵种全部消灭前只能攻击这一兵种，不能穿插攻击其他兵种。兵种内部可以自由选择目标。没有锁定时，可以攻击任意存活敌人；攻击 \(a_i\le0\) 的兵种不会产生锁定。

鲍里斯不能跳过攻击、攻击已经移除的敌人或在敌人全部消灭后继续战斗。生命值没有上限，但任何回合结算后都必须严格大于 \(0\) ，降至 \(0\) 也算失败。敌人的攻击作为整体同时结算，没有内部先后顺序。

在所有合法选择中，最大化战斗结束后的生命值；若无法完成任务，输出 leave! .

第一行依次包含五个整数 \(K,N,H,A,\Delta H\) ，即兵种数、敌人总数、鲍里斯初始生命值、每次攻击的伤害和可选的生命增量。

接下来 \(K\) 行，每行一个兵种名称及两个整数 \(h_i,a_i\) . 名称按 UTF-8 编码，区分大小写，互不相同，不含空白字符。

接下来 \(N\) 行，每行一个兵种名称，表示一名敌人。每个名称一定在兵种表中出现；某些兵种的实际数量可以为零。

能够完成任务时，输出最大最终生命值的十进制整数；否则输出 leave! .

合法答案可能超过 64 位整数范围。

2 3 100 50 100
YuriRecruit 20 30
GIGuard 80 10
YuriRecruit
YuriRecruit
GIGuard

选择增加生命，将生命值升到 \(200\) . 依次消灭两名 YuriRecruit 和一名 GIGuard ，最终剩余 \(140\) .

1 5 100 30 500
WarMiner 100 10
WarMiner
WarMiner
WarMiner
WarMiner
WarMiner

直接移除所有采矿车，战斗不产生任何回合。

3 5 100 100 500
Rocketeer 500 20
PrismTank 200 100
SEAL 50 100
Rocketeer
Rocketeer
PrismTank
SEAL
SEAL

leave!

不存在能够全程存活并消灭所有敌人的方案。

1 2 1 1 0
Medic 2 -10
Medic
Medic

先各攻击一次，两个敌人都保留，累计回复 \(40\) . 再逐一消灭，额外回复 \(10\) ，最终为 \(51\) .

\(1\le K\le5000\) ，\(1\le N\le50000\) .
\(1\le H\le10^9\) ，\(1\le A\le10^5\) ，\(0\le\Delta H\le10^9\) .
\(1\le h_i\le10^5\) ，\(-10^5\le a_i\le10^5\) ；攻击力为正的兵种至多 \(20\) 种。
每个名称为 \(1\) 至 \(100\) 个 UTF-8 字节，不含空格、制表符、换行等空白。
除名称外所有输入量均为整数，生命回复没有上限。

分值比例	额外条件
100%	无额外条件