Milk and Honey

Interview

Time limit1sMemory limit1024 MB

Summary

Each field holds either cows up to its cow limit or bees up to its bee limit; assign each field one animal type to maximize happiness from milk and honey.

Level: Easy3 of 10
Topics: Greedy, Sorting, Array, Implementation
Solved: No attempts yet

Problem

In the land of milk and honey, Juku is in charge of cows and bees. Bees sting cows and make them unhappy, and cows eat all the flowers that bees use to make honey, so cows and bees must be kept on separate fields.

Each field can support a limited number of animals. Cows and bees are free to obtain, so as many of them as a field can support are placed on it.

Each cow produces one unit of milk and each bee produces one unit of honey. Milk and honey produce different amounts of happiness when consumed.

Juku's task is to decide how to place cows and bees across the fields so that the total happiness is maximized. The calculations are too many to do on paper, so Juku needs your help.

Input

The first line contains two integers: $M$ ( $0 \le M \le 1000$ ), the happiness per unit of milk, and $H$ ( $0 \le H \le 1000$ ), the happiness per unit of honey.

The second line contains $N$ ( $1 \le N \le 1000$ ), the number of fields. Each of the following $N$ lines describes one field with two integers $C$ ( $0 \le C \le 100$ ) and $B$ ( $0 \le B \le 100$ ), the number of cows and the number of bees that field can support.

Output

Print a single integer: the maximum amount of happiness that can be achieved.

Examples2

Example 1
Input
```
3 5
3
4 2
3 2
2 1
```
Expected output
```
28
```
Example 2
Input
```
7 3
4
10 20
0 50
100 0
3 4
```
Expected output
```
941
```