Picture P23406


Statement
 

pdf   zip

thehtml

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

Public test cases
  • Input

    7 11
    3
    9 12
    6 15
    13 8
    

    Output

    104
    
  • Input

    200 450
    4
    500 300
    180 450
    450 400
    250 650
    
    10 10
    1
    20 20
    
    3 3
    0
    
    10 20
    1
    20 10

    Output

    150000
    400
    -1
    200
    
  • Information
    Author
    Anders Jonsson
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++ Java