小编Ahm*_*rif的帖子

我试图解决一个王国问题的辩护,并提出了一个算法,但它超过了问题的时间限制.

我想知道一个好的算法来在时间限制内解决这个问题.

问题:

西奥多实施了一个新的战略游戏"防御王国".在每个级别上,玩家保卫由矩形网格单元表示的王国.玩家在网格的某些单元格中构建弩塔.塔保护同一行和同一列中的所有单元格.没有两座塔共用一排或一列.

位置的惩罚是最大的不设防矩形中的单元格数.例如,图片上显示的位置有罚款12.

帮助西奥多编写一个计算给定位置罚分的程序.

输入

输入文件的第一行包含测试用例的数量.

每个测试用例由一个带有三个整数的线组成:w - 网格的宽度,h - 网格的高度和n - 弩塔的数量(1≤w,h≤40000;0≤n≤min(w, H)).

以下n行中的每一行包含两个整数xi和yi - 塔占据的单元的坐标(1≤xi≤w;1≤yi≤h).

产量

对于每个测试用例,输出一个整数 - 最大矩形中未由塔保护的单元格数.

例

输入:
1
15 8 3
3 8
11 2
8 6

产量:12