#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	char ch;
	while((ch=getchar())<'0'||ch>'9');
	int res=ch-'0';
	while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
	return res;
}	
const int M=1001000;
const int V=1000000;
int prm[100100],tot,pim[M];
void pre()
{
	pim[1]=1;
	for(int i=2;i<=V;i++)
	{
		if(!pim[i]) pim[i]=prm[++tot]=i;
		for(int j=1,tmp;j<=tot&&(tmp=prm[j]*i)<=V;j++)
		{
			pim[tmp]=prm[j];
			if(i%prm[j]==0) break;
		}
	}
}
int n,m,K,c[M],a[M];
struct Tree{
	int d[M];
	inline int lowbit(int x){ return x&-x; }
	void pre(){ for(int i=1;i<=m;i++) d[i]=1e9; }
	void upt(int x,int v)
	{
		for(int i=x;i<=m;i+=lowbit(i)) 
			d[i]=min(d[i],v);
	}
	int  qry(int x)
	{
		int res=1e9;
		for(int i=x;i;i-=lowbit(i)) res=min(res,d[i]);
		return res;
	}
}T;
int nn;
bool check(int x)
{
	int sum=0;
	for(int i=1;i<=nn;i++)
	{
		if(a[i]>x)
		{
			int tmp;
			if(x!=0) tmp=a[i]/x+(a[i]%x!=0);
			else tmp=a[i]+1;
			sum+=c[tmp];
			if(sum>K) break;
		}
	}
	return sum<=K;
}
int main()
{
	pre();
	int t=read();
	while(t--)
	{
		n=read();m=read();K=read();
		T.pre();nn=(n+1)/2;
		for(int i=1;i<=n;i++) a[i]=read();
		sort(a+1,a+1+n);
		for(int i=1;i<=m;i++) c[i]=read();
		c[1]=0;c[m+1]=1e9;
//		for(int i=1;i<=m;i++) T.upt(m+1-i,c[i]);
//		for(int i=2;i<=m;i++)
//		{
//			c[i]=min(c[i],T.qry(m+1-pim[i])+T.qry(m+1-i/pim[i]));
//			T.upt(m+1-i,c[i]);
//		}
//		for(int i=1;i<=m;i++) c[i]=T.qry(m+1-i);
		for(int i=m-1;i>=1;i--) c[i]=min(c[i],c[i+1]);
		for(int i=2;i<=m;i++)
		{
			c[i]=min(c[i],c[pim[i]]+c[i/pim[i]]);
			for(int j=1;j<i;j++) c[j]=min(c[j],c[i]);
		}
		int L=0,R=a[nn];
		while(L<=R)
 		{
 			int mid=L+R>>1;
			if(check(mid)) R=mid-1;
			else L=mid+1;	
		}
		printf("%d\n",R+1);
	}
	return 0;
}