Picture P23406

Charlotte fue de vacaciones al Machu Picchu y tomó una fotografía que quiere enmarcar para colgar de la pared. Naturalmente, quiere un marco que sea lo bastante grande como para contener su imagen, pero también desea que no sea mayor de lo necesario. Específicamente, quiere minimizar el área del marco. Tanto la fotografía como el marco son rectángulos cuyas dimensiones vienen descritas por dos números naturales. Escribe un algoritmo que encuentre, dada una secuencia de marcos, el área del marco más pequeño en el que quepa la fotografía.

Por ejemplo, si la fotografía mide 7 × 11 y hay tres marcos con dimensiones 9 × 12, 6 × 15, y 13× 8, Charlotte elegiría el último marco. El segundo es demasiado pequeño, y de los dos restantes el primero es el más grande (9*12 = 108, comparado con 13*8 = 104).

Entrada

Cada caso de la entrada empieza con dos números naturales X ≤ 1000 y Y ≤ 1000 describiendo las dimensiones de la fotografía. A continuación, sigue un número N ≤ 1000 de marcos en la tienda, y N líneas con dos números naturales A ≤ 1000 y B ≤ 1000 en cada una, describiendo las dimensiones de cada marco. La entrada puede contener diversos casos, separados entre sí por una línea en blanco; tu programa debe detectar cuándo finalizan los casos.

Salida

Para cada caso, escribe el área del más pequeño de los marcos en los que cabe la fotografía. Si ésta no cabe en ningún marco, escribe −1.

Autor: Anders Jonsson