Problem Description

In the “Smart Campus” project, it was decided to install a new-generation air conditioner in every classroom in the school for automatic cooling and ventilation. According to the design, each classroom can have only one air conditioner, and the air conditioner’s power must match the classroom size—the larger the classroom, the higher the required power.

The school’s classrooms are numbered consecutively from $1$ to $n$. It is known that classroom $i$ needs an air conditioner with power at least $a_i$ watts.

The school administration provides $m$ different air conditioner models for purchase. Each model has a corresponding power and price. Please write a program to compute the minimum total cost to equip all classrooms with air conditioners.

Input Format

The first line contains an integer $n\ (1 \le n \le 50\,000)$, the number of classrooms.

The second line contains $n$ integers $a_i\ (1 \le a_i \le 1000)$, where $a_i$ is the minimum required power (in watts) for the air conditioner in classroom $i$.

The third line contains an integer $m\ (1 \le m \le 50\,000)$, the number of available air conditioner models.

The next $m$ lines each contain two integers $b_j$ and $c_j\ (1 \le b_j \le 1000, 1 \le c_j \le 1000)$, where $b_j$ is the power (in watts) of model $j$ and $c_j$ is its price.

Output Format

Output one integer, the minimum total cost to equip all classrooms with air conditioners. It is guaranteed that there is at least one feasible solution that meets the requirements of all classrooms.

1
800
1
800 1000

1000

3
1 2 3
4
1 10
1 5
10 7
2 3

13

Hint

In the first sample, you can only buy the only available air conditioner, which costs $1000$ yuan.

In the second sample, the optimal solution is to install model $4$ in classrooms $1$ and $2$, and model $3$ in classroom $3$, for a total cost of $13$ yuan ($3 + 3 + 7$).

Scoring

For the $50$-point testdata, $n, m \le 1000$.

Translation source: GPT 4.1 mini.

Translated by ChatGPT 5