Maximum Non-Overlapping Rectangular Regions

You are given a rectangular garden with dimensions (N) (height) and (M) (width). Additionally, there are (K) types of plants. Each plant requires a rectangular region of size (h_i \times w_i) in the garden. The plant can be rotated by 90 degrees, meaning that a plant that requires (h_i \times w_i) can alternatively be planted in a region of size (w_i \times h_i).

Your task is to determine the maximum number of non-overlapping rectangular regions that can be allocated in the garden using exactly one of the plant types such that the allocated regions completely fill the garden in a grid-like manner. For each plant, if it fits in the garden, the number of regions that can fit is (\left\lfloor \frac{N}{h_i} \right\rfloor \times \left\lfloor \frac{M}{w_i} \right\rfloor) or, when rotated, (\left\lfloor \frac{N}{w_i} \right\rfloor \times \left\lfloor \frac{M}{h_i} \right\rfloor). Output the maximum such count among all plant types. If no plant can fit, output 0.

inputFormat

The input is provided on the standard input (stdin) in the following format:

• The first line contains two integers (N) and (M), representing the height and width of the garden respectively.
• The second line contains an integer (K), the number of plant types.
• The next (K) lines each contain two integers (h_i) and (w_i), representing the required dimensions for the (i)-th plant.

For example: 4 4 2 2 2 3 1

outputFormat

Output a single integer representing the maximum number of non-overlapping rectangular regions that can be arranged inside the garden using one selected plant type, considering both orientations. The result should be printed to standard output (stdout).## sample

4 4
2
2 2
3 1

4