题目描述

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

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

输入格式

输入按如下的格式给出：

| | | | | | :-: | :-: | :-: | :-: | :-: | :-: | | $N$ | | | | | $HP_1$ | | | | | $HP_2$ | | | | | ... | | | | | $HP_N$ | | | | | $M$ | | | | | $Name_1$ | $MP_1$ | $Target_1$ | $Damage_1$ | | $Name_2$ | $MP_2$ | $Target_2$ | $Damage_2$ | | ... | | | | | $Name_M$ | $MP_M$ | $Target_M$ | $Damage_M$ | N是怪兽的数量(1≤N≤100)，Hpi表示第i个怪兽的hit point(l≤HPi≤100000)，M表示可用的魔法数量(1<=M<=lOo)，Namej是第j种魔法的名字，最长会有30个大写或小写字母，MPj是这种魔法需要消耗的魔力(0 $MPj≤99)，Targetj要么是”Single”，要么是”All”，表示该魔法只攻击单个怪兽或对全体怪兽同时有效。Damagej表示对于所有玫击对象，可以减少攻击对象Damagej的hit point(0≤Damagej≤999999)。

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

输出格式

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

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

232