# 菁英战斗兵 - 参考时间限制：1.0 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估） - 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。 - 内存限制：128 MB ## 背景故事 鲍里斯和铁狗再次突入敌军重围。铁狗可以潜入指挥部，让一个兵种的全部单位瘫痪退出战斗，或者为鲍里斯增加生命值；剩下的工作则交给他的 AKM。 侦察机发回的情报里，敌军既有战斗单位，也有无法造成伤害的生产单位，甚至还有攻击反而会给鲍里斯回血的奇怪单位。任务要求一个不留，但可以讲究处理顺序。毕竟，“敌人的火力支援”偶尔也能按字面理解。 请计算鲍里斯完成任务后最多能剩下多少生命值。 ## 形式化问题描述 有 $K$ 种敌军单位，共 $N$ 个。兵种 $i$ 的每个单位初始生命值为 $h_i$ ，攻击力为 $a_i$ ；$a_i<0$ 表示它的攻击为鲍里斯回复生命。鲍里斯初始生命值为 $H$（Health），每次攻击造成 $A$（Attack）点伤害。 战斗开始前，铁狗执行以下两项中的一项，且仅执行一次： 1. 将一个兵种的所有单位直接移除，不消耗回合； 2. 将鲍里斯的生命值增加 $\Delta H$ ，其中 $\Delta H$ 是输入给定的生命增量。 只要还有敌人，每回合必须执行： 1. 鲍里斯选择一个存活敌人攻击；该敌人生命值降至非正时立即移除。 2. 所有仍存活敌人同时攻击，鲍里斯的生命值减去它们攻击力的总和；总和为负时即为回血。 若鲍里斯开始攻击一个 $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 位整数范围。 ## 样例 1 ### 输入 ```text 2 3 100 50 100 YuriRecruit 20 30 GIGuard 80 10 YuriRecruit YuriRecruit GIGuard ``` ### 输出 ```text 140 ``` ### 解释 选择增加生命，将生命值升到 $200$ . 依次消灭两名 `YuriRecruit` 和一名 `GIGuard` ，最终剩余 $140$ . ## 样例 2 ### 输入 ```text 1 5 100 30 500 WarMiner 100 10 WarMiner WarMiner WarMiner WarMiner WarMiner ``` ### 输出 ```text 100 ``` ### 解释 直接移除所有采矿车，战斗不产生任何回合。 ## 样例 3 ### 输入 ```text 3 5 100 100 500 Rocketeer 500 20 PrismTank 200 100 SEAL 50 100 Rocketeer Rocketeer PrismTank SEAL SEAL ``` ### 输出 ```text leave! ``` ### 解释 不存在能够全程存活并消灭所有敌人的方案。 ## 样例 4 ### 输入 ```text 1 2 1 1 0 Medic 2 -10 Medic Medic ``` ### 输出 ```text 51 ``` ### 解释 先各攻击一次，两个敌人都保留，累计回复 $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% | 无额外条件 |