1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=10005,maxl=105,maxk=25;
int n,l,m,a[maxk],p[maxk],len[maxl],vst[maxn],dist[maxn],Dist[maxk][maxk],f[1<<20],Log[1<<20];
void Bfs() {
for(int i=1; i<=n+1; i++)if(vst[i])p[m++]=i;
for(int i=0; i<m; i++) {
memset(dist,0x3f,sizeof(dist));
queue<int> Q;
Q.push(p[i]);
dist[p[i]]=0;
while(!Q.empty()) {
int now=Q.front();
Q.pop();
for(int j=1; j<=l; j++) {
if(now+len[j]<=n+1&&dist[now+len[j]]==0x3f3f3f3f) {dist[now+len[j]]=dist[now]+1;Q.push(now+len[j]);}
if(now-len[j]>=1&&dist[now-len[j]]==0x3f3f3f3f) {dist[now-len[j]]=dist[now]+1;Q.push(now-len[j]);}
}
}
for(int j=0; j<m; j++)Dist[i][j]=dist[p[j]];
}
}
void Clear() {
m=0;
memset(vst,0,sizeof(vst));
memset(Dist,0x3f,sizeof(Dist));
memset(f,0x3f,sizeof(f));
}
int main() {
for(int i=0; i<20; i++)Log[1<<i]=i;
int t=Get_Int();
while(t--) {
Clear();
n=Get_Int();
int k=Get_Int();
l=Get_Int();
for(int i=1; i<=k; i++)a[i]=Get_Int();
sort(a+1,a+k+1);
k=unique(a+1,a+k+1)-a-1;
for(int i=1; i<=k; i++)vst[a[i]]^=1,vst[a[i]+1]^=1;
for(int i=1; i<=l; i++)len[i]=Get_Int();
Bfs();
f[0]=0;
for(int S=1; S<(1<<m); S++) {
int u=Log[S&(-S)];
for(int i=u+1; i<m; i++)if(S>>i&1)f[S]=min(f[S],f[S^(1<<i)^(1<<u)]+Dist[u][i]);
}
printf("%d\n",f[(1<<m)-1]==0x3f3f3f3f?-1:f[(1<<m)-1]);
}
return 0;
}
|
