Picture P23406


Statement
 

pdf   zip

thehtml

Charlotte went on holidays to Machu Picchu and took a picture that wants to frame to hang it on the wall. Naturally, she wants a frame big enough to contains her picture, but also wants that it is not bigger than necessary. Specifically, she wants to minimize the area of a frame. The picture as well as the frame are rectangles which dimensions are described by two natural numbers. Write an algorithm that finds, given a sequence of frames, the area of the smallest frame in which fits the picture.

For instance, if the picture measures 7 × 11 and there are three frames with dimensions 9 × 12, 6 × 15, and 13× 8, Charlotte would choose the last frame. The second one is too small, and the other frames the first one is the biggest (9*12 = 108, compared with 13*8 = 104).

Input

Each case of the input starts with two natural numbers X ≤ 1000 and Y ≤ 1000 describing the dimensions of the picture. Then, a number N ≤ 1000 of frames in the shop follows, and N lines with two natural numbers A ≤ 1000 and B ≤ 1000 in each one, describing the dimensions of each frame. The input may contain various cases, separated between them by a line in white; your program must detect when the cases finish.

Output

For each case, your program must print the area of the smallest frame in which the picture fits. If it does not fit in any frame, it must print −1.

Author: 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
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++ Java