Problem B
Food Replicator

Living in SimCity¹, Henry has recently acquired a new food replicator and has decided to throw a party to show it off. His friends have come prepared: They have each brought a certain number of tokens to use in his machine (note that tokens are not the same as money).

Henry, being the good host he is, has decided to cover the financial costs for duplicating food. Unfortunately, he’s on a tight budget. He wants to make the most people happy given his financial constraints, but after looking at all the different factors, he is realizing it’s more complicated than he had thought.

In a given round, the duplicator will create $K$ batches of food, where $K$ is the amount of tokens in the machine. A single round of duplication costs a fixed amount of money, independent of how many batches are being produced. Henry’s friends have decided that they will insert a token (exactly one) for a given round if, and only if, he is duplicating their favorite food that round. To complicate things further, each different food type costs Henry a different amount of money to duplicate (due to differing ingredients).

Each friend receives $1$ point of happiness for every food they duplicate. They will always insert a token if their favorite food is being duplicated, but they stop inserting once they run out of tokens.

Frustrated at how complicated the calculations have become, Henry has decided to ask you to solve the problem for him. Help him maximize the total happiness or his party will be a complete disaster.

Input

The first line of input contains three space-separated integers; $M$, $N$, and $F$, where $M$ is the maximum amount of money that Henry is able to spend, $N$ is the number of types of food, and $F$ is how many of Henry’s friends are coming to the party. The second line contains space-separated integers $c_1, \ldots , c_ N$ corresponding to the price of each food type. The following $F$ lines each contain two integers $p_ j$ and $t_ j$ ($1 \le j \le F$), respectively indicating for a given friend their favorite food and how many tokens they have.

You are given that:

$1 \leq M, c_ i, t_ j \leq 100\, 000$

$1 \leq N \leq 100$

$1 \leq F \leq 1\, 000$

$0 \leq p_ j < N$

Output

Print the maximum happiness that Henry can provide at his party.

12 3 3
2 2 2
0 2
1 2
2 2

6

15 3 4
5 3 4
0 1
0 2
1 5
2 5

5

33 3 6
10 1 2
0 10
0 5
0 1
1 2
1 2
2 3

12