Chocolate bar#4148
The "Retreat" team is gearing up for the upcoming marathon, "Guess the Melody: Rock Version." To keep their energy up during the event, they've brought along a large rectangular chocolate bar with dimensions w \times h. They also have a list of pairs of numbers representing the sizes of chocolates they consider lucky. Before indulging in the chocolate, the team plans to divide the bar into these lucky chocolates. The process involves breaking the chocolate bar into parts along a line strictly parallel to one of its sides, and then further breaking each resulting part in the same manner.
Your task is to determine the maximum number of lucky chocolates the team can produce using this method. Note that chocolates obtained by rotating lucky ones are not considered lucky.
The first line of the input contains three integers , , and —the dimensions of the chocolate bar and the number of lucky chocolate sizes, respectively (1 \leq w, h \leq 300, 1 \leq n \leq w \times h). The next lines each contain a pair of integers w_i, h_i, which are the dimensions of the lucky chocolates (1 \leq w_i \leq w, 1 \leq h_i \leq h).
Output a single line with the maximum number of lucky chocolates into which the given bar can be divided.
Example 1