Description

Each monster has some HP. You can cast spells to reduce a monster’s HP. Each spell has a certain damage, meaning one cast reduces the target’s HP by that amount. A monster is defeated if and only if its HP is less than or equal to $0$. Casting a spell consumes mana. Because your mana is limited, you want to defeat all monsters using the minimum total mana. Write a program to accomplish this task.

Input Format

The input is given as follows: $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$ is the number of monsters ($1 \le N \le 100$). $HP_i$ is the HP of the $i$-th monster ($1 \le HP_i \le 10^5$). $M$ is the number of available spells ($1 \le M \le 100$). $Name_j$ is the name of the $j$-th spell, containing at most $30$ uppercase or lowercase letters. $MP_j$ is the mana cost of that spell ($0 \le MP_j < 100$). $Target_j$ is either Single or All, meaning the spell either targets a single monster (Single) or affects all monsters simultaneously (All). $Damage_j$ is the amount by which one cast reduces each affected target’s HP ($0 \le Damage_j < 10^6$). All numbers are integers. At least one spell has a nonzero $Damage$ value.

Output Format

Output one line containing a single integer, the minimum total mana required.

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

232

Hint

Translated by ChatGPT 5