HZNUOJ

时光老人扔炸弹

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:187     AC:73     Score:95.83

Description

    在ACM队里,aias最喜欢看室友打LOL,(aias本人是手残党)。最近,他看室友玩时光守护者的时候,发现该英雄挺有趣。于是,上网搜集时光守护者技能的信息。他突然发现了一个很有意思的技能--定时炸弹。该技能表现为:放置的炸弹将会使爆破半径内的生物都受到一定的伤害。这时,他的室友突然给他出了一个难题:地图上有一个长为x,宽为y的长方形小兵阵型,而炸弹只能放在该长方形的横中心线上(例如长为4,宽为2,那么你只能宽为1的地方放置炸弹)。现在,手里有n个炸弹,它们的爆破半径可能不同也可能相同,请用最少的炸弹数来杀死该长方形里的所有小兵。aias发现自己不会算,于是找你来帮忙,聪明如你,能不能帮他解决这个问题呢?

Input

先输入整数t代表接下来有t组测试数据(t<10);
每组测试数据由两行组成,第一行输入3个整数(x,y,n),x和y分别代表长方形的长和宽的大小,n代表炸弹的数量,并且满足x<=100,y<=100 ,n<=100, x>y;
第二行输入n个浮点数ri( ri<20),ri代表第i颗炸弹的爆破半径。.

Output

输出最少需要多少颗炸弹,如果没有则输出-1。

Samples

input
2 20 2 5 2 3.2 4 4.5 6 20 2 10 1 2 3 1 2 1.2 3 1.1 1 2
output
2 5

Author

YE, Lei

Source

杭州师范大学第九届程序设计竞赛