记录编号	577650	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2018]屠龙勇士	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	4.065 s
提交时间	2022-11-19 07:25:37	内存使用	6.51 MiB

#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int N=100000+5;
int n,m;
ll a[N],p[N],b[N],sw[N];
multiset<ll>s;
inline ll gcd(ll x,ll y){
	if (y==0)return x;
	return gcd(y,x%y);
}
inline void exgcd(ll x,ll y,ll &fx,ll &fy){
	if (y==0){
		fx=1;fy=0;return ;
	}
	exgcd(y,x%y,fy,fx);
	fy-=(x/y)*fx;
	return ;
}
inline ll read(){
	ll ans=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
inline void write(ll x){
	if (x<0)putchar('-'),x=-x;
	if (x>9)write(x/10);
	putchar(x%10+'0');
}
int main(){
	freopen ("2018dragon.in","r",stdin);
	freopen ("2018dragon.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		s.clear();
		bool ok=0;
		for (int i=1;i<=n;i++)a[i]=read();
		for (int i=1;i<=n;i++)p[i]=read();
		for (int i=1;i<=n;i++)b[i]=read();
		for (int i=1;i<=m;i++){
			ll x=read();
			s.insert(x);
		}
		multiset <ll>::iterator it;ll mn=0;
		for (int i=1;i<=n;i++){
			ll w=b[i];
			it=s.upper_bound(a[i]);
			if (it==s.begin()){
				b[i]=*it;s.erase(it);
			}
			else{
				it--;b[i]=*it;s.erase(it);
			}
			s.insert(w);
			mn=max(mn,a[i]/b[i]+(a[i]%b[i]>0));
		}
		
		for (int i=1;i<n;i++){
			ll p1=p[i],p2=p[i+1];
			ll a1=a[i],a2=a[i+1];
			ll b1=b[i],b2=b[i+1];
			ll d=gcd(b2*p1,b1*p2),c=b1*a2-b2*a1;
			
			if (c%d!=0){
				ok=1;printf("-1\n");break;
			}
			ll m1=b2*p1/d,m2=b1*p2/d;
			ll fx=1,fy=0;
			exgcd(m1,m2,fx,fy);
			p[i+1]=p[i]*p[i+1]*b1/d;
			a[i+1]=(c/d*fx%p[i+1]*p1%p[i+1]+a1)%p[i+1];
			a[i+1]%=p[i+1];
			b[i+1]=b[i];
		}
		if (ok==1)continue;
		ll d=gcd(b[n],p[n]);
		if (a[n]%d!=0){
			printf("-1\n");continue;
		}
		ll fx=1,fy=0;
		exgcd(b[n],p[n],fx,fy);
		ll ans=a[n]/d*fx,l=p[n]/d;
		ans=(ans%l+l)%l;
		write(max(ans,mn));putchar('\n');
	}
	return 0;
}