P1779 魔鬼杀手

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

每个怪兽都有一定的生命值。 你可以靠施魔法，减少怪兽的生命值。 每个魔法都会有一定的伤害，表示用该魔法进行一次攻击能使得被攻击者的生命值减少的数量。 一个怪兽被击败了当前仅当它的生命值小于等于 $0$。 魔法是要消耗魔力的。 因为你的魔力是有限的，你希望用最少的魔力击败所有的怪兽。 写一个程序完成这个任务。

输入按如下的格式给出： > $N$ > $HP_1$ > $HP_2$ > $\ldots$ > $HP_N$ > $M$ > $Name_1$ $MP_1$ $Target_1$ $Damage_1$ > $Name_2$ $MP_2$ $Target_2$ $Damage_2$ > $\ldots$ > $Name_M$ $MP_M$ $Target_M$ $Damage_M$ $N$ 是怪兽的数量（$1\le N\le 100$）。 $HP_{i}$ 表示第 $i$ 个怪兽的生命值（$l\le HP_i\le 10^5$）。 $M$ 表示可用的魔法数量（$1\le M\le 100$）。 $Name_j$ 是第 $j$ 种魔法的名字，最长会有 $30$ 个大写或小写字母。 $MP_j$ 是这种魔法需要消耗的魔力（$0\le MP_j

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