Biggest (Zero Carbon) Footprint

Time limit2sMemory limit512 MB

Summary

Given tree points in an n by m forest, find the largest axis-aligned rectangle with no tree strictly in its interior.

Level: Medium7 of 10
Topics: Geometry, Sorting, Brute force, Array
Solved: No attempts yet

Problem

You have just won the lottery and decide to build a summer resort deep in a forest. Being very eco-friendly, you refuse to cut down a single tree. Given a map of the forest and the positions of its trees, find the area of the largest rectangular plot of land you can buy that contains no tree in its interior. The plot's edges must be parallel to the $x$ - and $y$ -axes.

A tree that lies exactly on an edge of the plot is fine; only a tree strictly inside the plot is not allowed.

Input

The first line contains three integers $n$ , $m$ , and $t$ ( $0 < n, m < 10000$ , $0 < t < 10000$ ): the width and height of the forest map and the number of trees on it.

Each of the next $t$ lines contains two integers $x$ and $y$ ( $0 \le x \le n$ , $0 \le y \le m$ ), the position of one tree. The point $(0, 0)$ is the bottom-left corner of the map and the point $(n, m)$ is the top-right corner.

Output

Print a single integer: the area of the largest axis-aligned rectangle that contains none of the given trees in its interior.

Examples3

Example 1
Input
```
5 5 2
1 1
3 3
```
Expected output
```
12
```
Example 2
Input
```
10 10 2
1 5
9 5
```
Expected output
```
80
```
Example 3
Input
```
10 10 1
5 5
```
Expected output
```
50
```