Under construction

Still being built. Things may change

Glass cutting

Interview

Time limit1sMemory limit1024 MB

Summary
Given an M by N pane with K point defects, find the largest axis-parallel rectangle that has no defect strictly inside it.
Level

Medium5 of 10

Topics
Sorting, Brute force, Array
Solved
No attempts yet

Statement

Artūras built a frame for a new greenhouse and plans to glaze it. He bought a glass pane of size M×NM \times N (length MM, width NN), but at home he found KK defects in it. All defects are small, so treat each one as a point where the glass is slightly cracked.

Artūras does not want to use poor-quality glass, so he plans to cut out the largest possible rectangle from the pane that contains no defects.

Artūras has a device that holds the pane and makes straight cuts parallel to its edges, that is, horizontal and vertical cuts. The device is precise enough that a cut can pass through a defect without the glass breaking.

Compute the maximum area of a defect-free rectangle that Artūras can cut from the pane.

A defect may lie on the edge of the cut rectangle, but no defect may lie inside it.

Input

The first line contains three integers MM, NN, and KK. Each of the next KK lines contains two integers XX and YY, the coordinates of one defect.

The lower left corner of the original pane has coordinates (0,0)(0, 0), and the upper right corner has coordinates (M,N)(M, N).

It is always true that 1≤X≤M−11 \le X \le M-1 and 1≤Y≤N−11 \le Y \le N-1. All defect coordinates are distinct.

Output

Print one integer: the maximum area of a defect-free rectangle that Artūras can cut from the pane.

Constraints

2≤M,N≤300002 \le M, N \le 30000, 1≤K≤5001 \le K \le 500

Examples1

  1. Example 1

    Input
    8 4 2
    1 3
    7 2
    
    Expected output
    24