题目背景

你生活在一个怪兽世界里。

你需要用魔法反抗这些怪兽。

题目描述

每个怪兽都有一定的生命值。

你可以靠施魔法，减少怪兽的生命值。

每个魔法都会有一定的伤害，表示用该魔法进行一次攻击能使得被攻击者的生命值减少的数量。

一个怪兽被击败了当前仅当它的生命值小于等于 $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<100$）。

$Target_j$ 要么是 Single，要么是 All，表示该魔法只攻击单个怪兽（Single）或对全体怪兽同时有效（All）。

$Damage_j$ 表示该魔法进行一次攻击能使得被攻击者的生命值减少的数量（$0\le Damage_j<10^6$）。

所有数字都是整数。

最少有一种魔法的 $Damage$ 值是非零的。

输出格式

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

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

232