Minimum Mana to Defeat All Monsters

You live in a world filled with monsters. Each monster has a certain number of hit points (HP) that represent its life. You can cast spells in order to reduce a monster's hit points. Every spell has a specific damage value and costs some amount of mana. A monster is considered defeated if its hit points become less than or equal to 0.

Your objective is to defeat all the monsters using the least amount of mana possible. Since your mana is limited, you must choose your spells optimally. You are allowed to use each spell an unlimited number of times.

Input Format: The input begins with an integer n representing the number of monsters, followed by n integers representing each monster's hit points. Next, an integer m is given which represents the number of available spells. The following m lines each contain two integers: d and c, where d denotes the damage the spell inflicts and c denotes the mana cost of the spell.

Mathematical Formulation:
Given a monster with hit points \(H\), and spells \(\{(d_i, c_i)\}_{i=1}^m\), determine the minimum mana \(M\) such that there exists a sequence of spells with total damage \(\ge H\) and total mana cost \(M\). The overall answer is the sum of the minimum mana required for each monster.

Output Format: A single integer representing the minimum total mana required to defeat all the monsters.

inputFormat

The first line contains an integer n (\(1 \le n \le 10^5\)), representing the number of monsters. The second line contains n space-separated integers where each integer represents the hit points of a monster.

The third line contains an integer m (\(1 \le m \le 100\)), representing the number of spells available. This is followed by m lines, each containing two space-separated integers \(d\) and \(c\) (\(1 \le d, c \le 10^9\)) representing the damage and mana cost of each spell, respectively.

outputFormat

Output a single integer, which is the minimum total mana required to defeat all monsters.

sample

1
10
2
3 5
5 9

18