Problem Description

At my favorite restaurant, you can get tickets by having meals.

There are two types of tickets: special tickets essential for exchanging toppings, and regular tickets.

The restaurant has $ N $ types of toppings, and topping $ i $ can be obtained by exchanging it for $ t_i $ tickets. The restaurant allows you to combine tickets to get multiple types of toppings, but you cannot get the same topping more than once.

When exchanging, both special and regular tickets are counted as one ticket each, but for each topping, the tickets used must include at least one special ticket. For example, if a topping can be exchanged for 4 tickets, the following 4 ways of exchange are possible:

• A combination of 1 special ticket and 3 regular tickets.
• A combination of 2 special tickets and 2 regular tickets.
• A combination of 3 special tickets and 1 regular ticket.
• A combination consisting of only 4 special tickets.

Each topping has a positive integer value called happiness, and the happiness of getting topping $ i $ is $ h_i $.

Today is a special day, so I want to use my tickets wisely to maximize the total happiness of the toppings I get. Write a program that calculates the maximum possible total happiness from the information about tickets and toppings.

Input Format

The input is given from the standard input in the following format:

$ X $ $ Y $ $ N $ $ t_1 $ $ h_1 $ $ t_2 $ $ h_2 $ : $ t_N $ $ h_N $

• The first line contains two integers $X\ (1\ ≦\ X\ ≦\ 300)$ and $Y\ (0\ ≦\ Y\ ≦\ 300)$ separated by a space, representing the number of special tickets and regular tickets you initially have, respectively.
• The second line contains an integer $N\ (1\ ≦\ N\ ≦\ 300)$, representing the number of types of toppings.
• The next $ N $ lines contain two integers $t_i\ (1\ ≦\ t_i\ ≦\ 600)$ and $h_i\ (1\ ≦\ h_i\ ≦\ 5,000,000)$ separated by a space, representing that topping $ i $ can be obtained by exchanging it for $ t_i $ tickets, and the happiness gained from getting it is $ h_i $.

Output Format

Output the maximum possible total happiness on one line. Make sure to include a newline at the end of the output.

Sample Input and Output

Sample Input #1

3 5
4
3 30
3 40
5 60
7 80

Sample Output #1

100

Sample Input #2

3 3
4
3 30
3 40
5 60
7 80

Sample Output #2

70

Sample Input #3

1 5
4
3 30
3 40
5 60
7 80

Sample Output #3

60

Sample Input #4

6 12
4
3 30
3 40
5 60
7 80

Sample Output #4

210

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $X\ ≦\ 50$, $Y\ ≦\ 50$, $N\ ≦\ 50$, $t_i\ ≦\ 100\ (1\ ≦\ i\ ≦\ N)$, you will be awarded 30 points.
• If you solve the dataset without additional constraints, you will be awarded an additional 70 points.

Sample Explanation 1

In the initial state, you have 3 special tickets and 5 regular tickets. For example, the following exchanges can achieve the maximum value of 100 (40 + 60):
- Get topping 2 (requires 3 tickets) by exchanging 1 special ticket and 2 regular tickets. The happiness of topping 2 is 40.
- Get topping 3 (requires 5 tickets) by exchanging 2 special tickets and 3 regular tickets. The happiness of topping 3 is 60.
This method consumes 3 (1 + 2) special tickets and 5 (2 + 3) regular tickets, which is feasible.

Sample Explanation 2

Getting toppings 1 and 2 is the optimal solution.

Sample Explanation 3

Getting topping 3 and leaving 1 ticket is the optimal solution.

Sample Explanation 4

You can get all the toppings.

见题面 Input 部分

见题面 Output 部分