#2421. Paint

内存限制:128 MiB 时间限制:20 Sec

题目描述

话说今年HNOI省队集训在一中进行,为此,fmsoi特意准备了一个巨大的电子广告牌,准备在上面写着“一中欢迎你”。
       但是这块牌子却出现了问题,经过神一般的小Y的修理后,终于好了,可是却恢复到了默认状态---没有显示任何字了。显然我们还要让它显示出“一中欢迎你”。
       众所周知,这类广告牌通常由若干像素点构成,我们考虑其中的一行,最开始每一行都是不发光的。
       每一行有N个像素点,将其标号1..N。现在给定K个点,要求这K个点发光,其余点不能发光。而这个电子广告牌的操作方式比较畸形,它有L种操作方法,第i种为U­­i ,即你能将任意长为U­­i 的连续一段的像素状态取反,即改变发光状态。
       现在你被分配了要处理好不同的T行,为了节省时间,对于每一行你都必须用最少的操作次数。

输入格式

       第一行一个数T,表示数据组数
       然后是T组数据描述,对于每组数据:
       第一行为N,K,L,即一行有N个点,要求K个点必须发光,有L种操作方式。
       第二行K个数,表示要求发光的K个点。
       第三行L个数,表示L种操作。

输出格式

       包含T个数,每个一行,即对于每一组数据的最少操作次数。
       如果无法完成,请输出-1

样例

样例输入


			
2
10 8 2
1 2 3 5 6 7 8 9
3 5
3 2 1
1 2
3

样例输出


			
2
-1
【数据规模】
有20%较小的数据
对于100%的数据:
T<=10
N<=10000
K<=10,L<=100,1<=Ui<=N

数据范围与提示