Defense of a Kingdom

Time limit3sMemory limit256 MB

Summary

Given tower positions that block whole rows and columns on a grid, find the area of the largest rectangle of cells left undefended.

Level: Medium5 of 10
Topics: Sorting, Greedy, Array
Solved: No attempts yet

Problem

Theodore is building a new strategy game called "Defense of a Kingdom". On each level the player defends a Kingdom represented by a rectangular grid of cells. The player builds crossbow towers in some cells of the grid. A tower defends every cell in its own row and its own column. No two towers share a row or a column.

The penalty of a position is the number of cells in the largest undefended rectangle. For example, the position shown in the picture below has penalty 12.

Help Theodore write a program that computes the penalty of a given position.

Input

The first line contains three integers: w — the width of the grid, h — the height of the grid, and n — the number of crossbow towers (1 ≤ w, h ≤ 40000; 0 ≤ n ≤ min(w, h)).

Each of the next n lines contains two integers xi and yi — the coordinates of the cell occupied by a tower (1 ≤ xi ≤ w; 1 ≤ yi ≤ h).

Output

Print a single integer — the number of cells in the largest rectangle that is not defended by any tower.

Examples4

Example 1
Input
```
15 8 3
3 8
11 2
8 6
```
Expected output
```
12
```
Example 2
Input
```
5 5 0
```
Expected output
```
25
```
Example 3
Input
```
10 10 1
5 5
```
Expected output
```
25
```
Example 4
Input
```
20 10 2
5 3
15 7
```
Expected output
```
27
```