P1779 Demon Slayer

You live in a world of monsters. You need to fight back against these monsters using magic.

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.

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 one line containing a single integer, the minimum total mana required.

Translated by ChatGPT 5