损坏的牛棚
时间限制:1秒 内存限制:256M
【题目描述】
FJ买了一个矩形的 \(n\) 行 \(m\) 列的牧场。不幸的是,他发现某些 1 x 1 的区域被损坏了,所以它不可能在把整个牧场建造成牛棚了。 FJ数了一下,发现有 \(p\) 个 1 x 1 的损坏区域。
现请你帮助他找到不包含损坏区域的面积最大的矩形的牛棚。
【输入格式】
第 \(1\) 行: 三个空格隔开的整数 \(n, m\)和 \(P\)。
第 \(2..p+1\) 行: 每行包含两个空格隔开的整数:\(x y\),给出一个损坏区域的行号和列号。对同一个损坏区域可能有多次描述。
【输出格式】
牛棚的最大可能面积
【输入输出样例】
Input
3 4 2
1 3
2 1
Output
6
【子任务】
测试点1:\(n=5, m=6, p=5\)
测试点2:\(n=10, m=10, p=10\)
测试点3:\(n=20, m=15, p=17\)
测试点4:\(n=50, m=50, p=100\)
测试点5:\(n=98, m=100, p=1089\)
测试点6:\(n=50, m=300, p=3000\)
测试点7:\(n=1000, m=1000, p=5000\)
测试点8:\(n=2000, m=1500, p=25000\)
测试点9:\(n=3000, m=2500, p=30000\)
测试点10:\(n=3000, m=3000, p=100000\)
【来源】
Mr.he