Under construction

Still being built. Things may change

Paper Cutting

Interview

Time limit1sMemory limit128 MB

Summary
Given a rectangular sheet and a series of horizontal or vertical cuts along grid lines, compute the area of the largest resulting piece.
Level

Easy3 of 10

Topics
Sorting, Array, Math
Solved
No attempts yet

Problem

There is a rectangular sheet of paper as shown in <Figure 1>. The sheet has dotted lines at every 1 cm in both the horizontal and vertical directions. Horizontal dotted lines are numbered from top to bottom starting at 1, and vertical dotted lines are numbered from left to right starting at 1.

The paper is cut along dotted lines. A horizontal cut goes from the left edge to the right edge in one straight cut, and a vertical cut goes from the top edge to the bottom edge in one straight cut. For a sheet that is 10 cm wide and 8 cm tall, cutting along horizontal line 3, vertical line 4, and horizontal line 2 divides the sheet as shown in <Figure 2>. The largest resulting piece has area 30 cm².

Given the width and height of the sheet and the dotted lines to cut, write a program that finds the area in cm² of the largest resulting piece.

Input

The first line contains two natural numbers, the width and height of the sheet, in that order. Each length is at most 100 cm.

The second line contains the number of dotted lines to cut. Each of the following lines describes one dotted line. A horizontal cut is given as 0 followed by the line number, and a vertical cut is given as 1 followed by the line number. The two numbers on each line are separated by one space.

Output

Print the area of the largest paper piece on the first line. Do not print the unit.

Examples1

  1. Example 1

    Input
    10 8
    3
    0 3
    1 4
    0 2
    
    Expected output
    30