「SOL」屠龍勇士(LOJ)

multiset 內部每個位置儲存了一個元素（并不是把相同的元素合到同一個位置并且記錄次數），因此用迭代器 iterator 訪問其中的某個位置，訪問到的是單個元素，如果按迭代器順序訪問 multiset，就相當于把插入的所有元素排了個序，

multiset 內置有 lower_bound 和 upper_bound 函式，前者回傳第一個大于等于給定值的元素的迭代器，后者回傳第一個嚴格大于給定值的元素的迭代器，

multiset 的 delete 函式有兩類引數，第一類是給定數值，會洗掉其中所有該數值；第二類是給定迭代器，會洗掉迭代器對應的元素——這樣就只會刪掉一個數字，

利用這些特點，我們可以用 upper_bound 找到第一把攻擊力大于龍的生命值的劍，而上一把劍就是攻擊力小于等于生命值的劍，然后用 delete 洗掉該劍的迭代器（不能是數值！），

/*Lucky_Glass*/
#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

template<class T>T rin(T &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}
typedef long long llong;
const int N=1e5+10;
#define con(type) const type &

multiset<llong> sword;
int n,m;
llong ih[N],rec[N],rew[N],atk[N];

llong ina_GCD(con(llong)a,con(llong)b){return b?ina_GCD(b,a%b):a;}
llong ex_GCD(con(llong)a,con(llong)b,llong &x,llong &y){
	if(!b){x=1,y=0;return a;}
	llong ret=ex_GCD(b,a%b,x,y);
	swap(x,y);
	y-=a/b*x;
	return ret;
}
llong ina_ABS(con(llong)a){return a<0?-a:a;}
llong mul(llong a,llong b,llong mod){
	bool neg=(a<0)^(b<0);
	a=ina_ABS(a),b=ina_ABS(b);
	a%=mod,b%=mod;
	llong ret=0;
	while(b){
		if(b&1) ret=(ret+a)>=mod? ret+a-mod:ret+a;
		a<<=1,b>>=1;
		if(a>=mod) a-=mod;
	}
	if(neg && ret) return mod-ret;
	return ret;
}
pair<llong,llong> comb_CRT(con(llong)m0,con(llong)r0,con(llong)m1,con(llong)r1){
	llong g=ina_GCD(m0,m1);
	if((r1-r0)%g){
		// printf("(%lld,%lld)=%lld %lld %lld\n",m0,m1,g,r1,r0);
		return make_pair(-1ll,-1ll);
	}
	llong p,q;
	ex_GCD(m0/g,m1/g,p,q);
	p=mul((r1-r0)/g,p,m1/g);
	llong m2=m0/g*m1,r2=(mul(p,m0,m2)+r0)%m2;
	if(r2<0) r2+=m2;
	return make_pair(m2,r2);
}
llong solve(){
	sword.clear();
	rin(n),rin(m);
	for(int i=1;i<=n;i++) rin(ih[i]);
	for(int i=1;i<=n;i++) rin(rec[i]);
	for(int i=1;i<=n;i++) rin(rew[i]);
	for(int i=1,tmp;i<=m;i++) sword.insert(rin(tmp));
	for(int i=1;i<=n;i++){
		multiset<llong>::iterator it=sword.upper_bound(ih[i]);
		if(it!=sword.begin()) it--;
		atk[i]=*it;
		sword.erase(it);
		sword.insert(rew[i]);
	}
	llong mnbon=0;
	pair<llong,llong> now(-1ll,-1ll);
	for(int i=1;i<=n;i++){
		mnbon=max(mnbon,(ih[i]+atk[i]-1)/atk[i]);
		llong k=atk[i],r=ih[i],m=rec[i];
		// printf("%lld x = %lld (mod %lld) -> ",k,r,m);
		//kx = r (mod m)
		k%=m,r%=m;
		if(!k){
			if(r){
				// printf("A\n");
				return -1ll;
			}
			continue;
		}
		llong g=ina_GCD(k,m);
		if(r%g){
			// printf("B\n");
			return -1ll;
		}
		k/=g,m/=g,r/=g;
		llong invk,non;
		ex_GCD(k,m,invk,non);
		invk=(invk%m+m)%m;
		r=mul(r,invk,m);
		// printf("x = %lld (mod %lld)\n",r,m);
		pair<llong,llong> tmp(m,r);
		if(i==1) now=tmp;
		else now=comb_CRT(now.first,now.second,tmp.first,tmp.second);
		if(now.first==-1){
			// printf("C\n");
			return -1ll;
		}
	}
	if(now.first==-1) return mnbon;
	if(now.second>=mnbon) return now.second;
	else{
		llong k=(mnbon-now.second+now.first-1)/now.first;
		return now.second+k*now.first;
	}
}
int main(){
	// freopen("input.in","r",stdin);
	freopen("dragon.in","r",stdin);
	freopen("dragon.out","w",stdout);
	int cas;rin(cas);
	while(cas--) printf("%lld\n",solve());
	return 0;
}