1494: 矩形覆盖
题目描述
【问题描述】(这里所有的矩形，就相当于一个长方形)
学校门口路面上出现了一个矩形大洞。现在学校找来了一些矩形钢板，想要盖住这个大洞。可是，他们又想不出一个既安全又节省的覆盖方案，所以，找到了参加程序设计竞赛的你，帮忙设计一个覆盖方案。
从安全角度考虑，钢板的放置必须符合如下所有原则：
-
钢板之间可以相互叠加。
-
钢板必须完全覆盖大洞。
-
你可以任意旋转每块钢板，但是覆盖过程中，钢板的边必须与大洞的边平行。
-
每块钢板的4个角必须严格落在大洞外（钢板任何一个角和洞口的角重合，或者在大洞内部，这块钢板就会不稳定）
如下图所示几种放置方法，黑色表示大洞区域，红色表示钢板：
图A和B中，都有钢板的点在大洞内部，不能这样放置。图C和D中，钢板4个角都在大洞外，是稳定安全的。图E中，也是不稳定的，就算钢板的角在其他钢板上，也要落在大洞外。
请问能否在安全的前提下，用这些钢板盖住这个大洞，若可以，使用最少的钢板数量进行覆盖。请你帮忙计算一下！
输入
第一行两个整数R和C，表示大洞的长和宽。
第二行一个整数N，表示矩形钢板数量
接下来N行，每行两个整数w[i]和h[i]，表示第i块钢板的长和宽。
输出
要覆盖大洞最少使用钢板的数量，若无法覆盖，输出-1.
样例输入 复制
5 5
3
8 2
8 3
8 4
样例输出 复制
2
提示
【输入输出样例1】
|
cover.in |
cover.out |
|
5 5 3 8 2 8 3 8 4 |
2 |
【样例1解释】
任意选择两个钢板就可以盖住这个大洞。例如用最小的两个（8,2）和（8,3）钢板刚好覆盖如下图：
【输入输出样例2】
|
cover.in |
cover.out |
|
10 10 4 6 6 6 6 6 6 6 6 |
-1 |
【样例2解释】
无法覆盖，任何一个钢板都无法放上去。无法使钢板的四个角都落在大洞外。
【数据范围】
30%的数据，1<=R,C<=1000，1<=w[i]<=1000,h[i]=1。
70%的数据，n<=20,1<=R,C<=1000，1<=w[i],h[i]<=1000。
100%的数据1<=n<=50，1<=R,C,w[i],h[i]<=1000000000。