#P1779. 魔鬼杀手
魔鬼杀手
题目描述
你生活在一个怪兽世界里。你需要用魔法反抗这些怪兽。
每个怪兽都有一定的 hit points,表示他们的生命值。你可以靠施魔法,降低怪兽的 hit points。每个魔法都会有一定的 damage,表示会减少被攻击者 damage 的 hit point。一个怪兽被击败了当前仅当它的 hitpoint 小于等于 0。另一方面,魔法是要消耗魔力的。因为你的魔力是有限的,你希望用最少的魔力击败所有的怪兽。写一个程序完成这个任务。
输入格式
输入按如下的格式给出:
... | |||
... | |||
是怪兽的数量(), 表示第 个怪兽的 hit point(), 表示可用的魔法数量(), 是第 种魔法的名字,最长会有 个大写或小写字母, 是这种魔法需要消耗的魔力(), 要么是 "Single",要么是 "All",表示该魔法只攻击单个怪兽或对全体怪兽同时有效。 表示对于所有玫击对象,可以减少攻击对象 的 hit point()。
所有数字都是整数。最少有一种魔法的 是非零的。
输出格式
输出一行,包含一个整数,表示最小需要消耗的魔力。
3
8000 15000 30000
3
Flare 45 Single 8000
Meteor 62 All 6000
Ultimate 80 All 9999
232