Minimum Serving Cost

Boris is planning to host several dinners and must decide which serving dish to use for each dinner. For each dinner, he has a specific number of servings to prepare. There are different serving dishes available, where each dish has a defined capacity (the number of servings it can hold) and a cost. Boris wants to choose a dish for each dinner such that its capacity is at least the number of required servings, and the overall cost across all dinners is minimized.

Problem Details:

• For each dinner, select one dish whose capacity is greater than or equal to the required number of servings.
• If there are multiple dish options that satisfy the requirement, choose the one with the lowest cost.
• The goal is to minimize the total cost for hosting all dinners.

The problem can be modeled mathematically as follows: For each dinner with required servings \(r_i\), choose a dish \((c, cost)\) such that \(c \ge r_i\) and the sum \(\sum cost\) is minimized.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains an integer (n), the number of dinners to host.
2. The second line contains (n) space-separated integers representing the servings required for each dinner.
3. The third line contains an integer (m), the number of available dish types.
4. The next (m) lines each contain two space-separated integers, where the first integer is the dish's capacity and the second integer is its cost.

Example: 2 10 20 3 5 50 10 80 20 150

outputFormat

Output a single integer to standard output (stdout), representing the minimum total cost required to serve all dinners.## sample

2
10 20
3
5 50
10 80
20 150

230