Two Stickers

Interview

Time limit2sMemory limit512 MB

Summary

Given an H by W grid and N rectangles that may rotate, place two non-overlapping rectangles inside and maximize their total area.

Level: Medium5 of 10
Topics: Implementation, Brute force, Greedy, Geometry
Solved: No attempts yet

Problem

There is a grid paper of size H×W and N stickers. The size of the i-th sticker is Ri×Ci. The grid paper is divided into cells of size 1×1, with lines drawn at intervals of 1.

Today you want to attach two stickers to the grid paper. The sides of a sticker must align with the grid lines, and the two stickers must not overlap. However, the stickers may touch. A sticker may be rotated 90 degrees. A sticker cannot go outside the grid paper.

Find the maximum total area covered by the two attached stickers.

Input

The first line gives the size of the grid paper, H and W, and the second line gives the number of stickers, N. The following N lines give the sizes of the stickers, Ri and Ci.

Output

On the first line, print the maximum total area covered by the two attached stickers. If the two stickers cannot be attached, print 0.

Constraints

1 ≤ H, W, N ≤ 100
1 ≤ Ri, Ci ≤ 100

Examples3

Example 1
Input
```
2 2
2
1 2
2 1
```
Expected output
```
4
```
Example 2
Input
```
10 9
4
2 3
1 1
5 10
9 11
```
Expected output
```
56
```
Example 3
Input
```
10 10
3
6 6
7 7
20 5
```
Expected output
```
0
```