一个矩形谷仓

Mircea Pasoi – 2003

作为一个资本家，农夫约翰想通过购买更多的奶牛来扩大他的挤奶业务。他需要空间来为奶牛建造一个新谷仓。

FJ 购买了一块矩形田地，有 R (1 ≤ R ≤ 3,000) 行，编号 1..R，以及 C (1 ≤ C ≤ 3,000) 列，编号 1..C。不幸的是，他后来才发现田地里有些 1x1 的区域已经损坏，因此他不能在整块 R×C 的田地上建造谷仓。

FJ 统计出了 P (0 ≤ P ≤ 30,000) 个损坏的 1x1 地块，并请求你的帮助，找出他能在自己的土地上建造的最大矩形谷仓（即最大的面积），且不能建在损坏的地块上。

程序名称：rectbarn

输入格式

• 第1行：三个空格分隔的整数：R, C, P。
• 第2..P+1行：每行包含两个空格分隔的整数 r 和 c，表示损坏地块的行号和列号。

样例输入（文件 rectbarn.in）

3 4 2
1 3
2 1

输出格式

• 第1行：新谷仓的最大可能面积。

样例输出（文件 rectbarn.out）

6

输出说明

  1 2 3 4
 +-+-+-+-+
1| | |X| |
 +-+-+-+-+
2|X|#|#|#|
 +-+-+-+-+
3| |#|#|#|
 +-+-+-+-+

标记为 'X' 的地块是损坏的，标记为 '#' 的地块是新谷仓的一部分。