#P1779. 魔鬼杀手

魔鬼杀手

题目描述

你生活在一个怪兽世界里。你需要用魔法反抗这些怪兽。

每个怪兽都有一定的 hit points,表示他们的生命值。你可以靠施魔法,降低怪兽的 hit points。每个魔法都会有一定的 damage,表示会减少被攻击者 damage 的 hit point。一个怪兽被击败了当前仅当它的 hitpoint 小于等于 0。另一方面,魔法是要消耗魔力的。因为你的魔力是有限的,你希望用最少的魔力击败所有的怪兽。写一个程序完成这个任务。

输入格式

输入按如下的格式给出:

NN
HP1HP_1
HP2HP_2
...
HPNHP_N
MM
Name1Name_1 MP1MP_1 Target1Target_1 Damage1Damage_1
Name2Name_2 MP2MP_2 Target2Target_2 Damage2Damage_2
...
NameMName_M MPMMP_M TargetMTarget_M DamageMDamage_M

NN 是怪兽的数量(1N1001\le N\le 100),HPiHP_{i} 表示第 ii 个怪兽的 hit point(lHPi100000l\le HP_i\le 100000),MM 表示可用的魔法数量(1M1001\le M\le 100),NamejName_j 是第 jj 种魔法的名字,最长会有 3030 个大写或小写字母,MPjMP_j 是这种魔法需要消耗的魔力(0MPj990\le MP_j\le 99),TargetjTarget_j 要么是 "Single",要么是 "All",表示该魔法只攻击单个怪兽或对全体怪兽同时有效。DamagejDamage_j 表示对于所有玫击对象,可以减少攻击对象 DamagejDamage_j 的 hit point(0Damagej9999990\le Damage_j\le 999999)。

所有数字都是整数。最少有一种魔法的 DamageDamage 是非零的。

输出格式

输出一行,包含一个整数,表示最小需要消耗的魔力。

3
8000 15000 30000
3
Flare 45 Single 8000
Meteor 62 All 6000
Ultimate 80 All 9999
232