El famoso escultor griego de la antigüedad Phidias se está preparando para construir otro monumento maravilloso. Con este propósito él necesita placas de mármol rectangulares de lados \(W_1 × H_1 , W_2 × H_2 , ..., W_N × H_N\).

Hace poco, Phidias ha recibido una losa rectangular de mármol. El quiere cortar esta losa para obtener placas de los tamaños deseados. Cualquier pieza de mármol (la losa o las placas cortadas de ella) puede ser cortada vertical u horizontalmente en dos placas rectangulares con ancho y largo enteros, cortando completamente a través de esa pieza. Esta es la única forma de cortar piezas y las piezas no pueden ser unidas entre si. Debido a que el mármol tiene vetas en él, las placas no pueden ser rotadas: si Phidias corta una placa de tamaño \(A × B\) entonces no puede ser usada como una placa de tamaño \(B × A\) a menos que ~A = B~. El puede hacer cero o más placas de cada tamaño deseado. Una placa de mármol se desperdicia si no es de ninguno de los tamaños deseados después que se terminen los cortes. Phidias quiere saber como cortar la losa inicial de tal manera que sea desperdiciado tan poco mármol como sea posible.

Como un ejemplo, asuma que en la figura a continuación el ancho de la losa original es 21 y la altura de la losa original es 11, y los tamaños deseados de placa son 10 × 4, 6 × 2,7 × 5, y 15 × 10. La mínima cantidad de área desperdiciada es 10, y la figura muestra una secuencia de cortes con un área total desperdiciada de 10.

Su tarea consiste en escribir un programa que, dado el tamaño de la losa original y los tamaños deseados de placas, calcule el área total mínima de la losa original que debe ser desperdiciada.

Entrada

La primera línea de la entrada contiene dos enteros: primero ~W~, el ancho de la losa original y luego ~H~, la altura de la losa original. La segunda línea contiene un entero ~N~: el número de tamaños deseados de placas. Las siguientes ~N~ líneas contienen los tamaños deseados de placas. Cada una de estas líneas contienen dos enteros: primero el ancho ~W_i~ y luego la altura ~H_i~ del tamaño deseado de placa ~(1 \leq i \leq N)~.

Salida

La salida contiene una línea con un solo entero: el área total mínima de la loza original que debe ser desperdiciada .

Entrada

21 11
4
10 4
6 2
7 5
15 10

Salida

10

Restricciones

En todas las entradas, ~1 \leq W \leq 600~, ~1 \leq H \leq 600~, ~0 < N \leq 200~, ~1 \leq W_i \leq W~, y ~1 \leq H_i \leq H~.