#P18367. Furniture
Furniture
Furniture
题目描述
Bajtazar 为公寓订购了 件家具,想把它们全部放进一个大小为 的矩形客厅。第 件家具是一个大小为 的矩形。
每件家具都必须靠着两面长度为 的墙中的某一面摆放,并且必须让长度为 的边紧贴这面墙。也就是说,沿墙方向占用 ,向房间内部延伸 ,不能改为让长度为 的边贴墙。
所有家具必须完全位于客厅内部。任意两件家具不能有面积为正的重叠,但可以沿边接触,也可以只在角点接触。
判断能否摆下所有家具。你需要处理 组独立测试数据。
输入格式
第一行一个整数 ,表示测试数据组数。
每组数据第一行三个整数 ,分别表示客厅的尺寸和家具件数。
接下来 行,第 行两个整数 ,表示第 件家具的尺寸。
输出格式
输出 行。对于每组数据,若能摆下全部家具,输出 TAK;否则输出 NIE。
数据范围
- 。
- 。
- 。
- ,。
- 一个输入文件中,所有测试数据的 之和不超过 。
样例输入 1
4
9 7 6
2 2
3 2
4 5
1 5
1 3
6 2
3 3 3
3 1
1 1
3 1
3 3 3
1 3
1 3
1 3
3 3 2
2 2
2 2
样例输出 1
TAK
NIE
TAK
NIE
样例解释
第一组数据的一种合法摆放方式如下。图中每个小格的边长为 1,客厅宽 9、高 7;家具均以长度为 的边贴着上墙或下墙。
