题解：
求解形如 $A[i]ansequiv b[i](mod$ $p[i])$ 的 $x$ 的最小正整数解.
考虑只有一个等式，那么可以直接化成 $exgcd$ 的形式：
$A[i]ans+p[i]y=b[i],$ 直接求 $ans$ 的正整数解即可. 增量 $M$ 为 $frac{p[i]}{gcd(A[i],p[i])}$
那如果有多个式子呢 $?$
假设前面的式子得到的最小解为 $ans,$ 增量为 $M.$
考虑将当前求出的 $ans',M'$ 与 $ans$ 合并.
即 $ans+M imes x=ans'+M' imes yRightarrow Mx-M'y=ans'-ans.$
这个可以再用一次 $exgcd$ 解出来，然后新的增量为 $lcm(M,M')$.
主要就是这些，然后有一些细节和特判需要特别注意一下.
#include <set>
#include <cstdio>
#include <string>
#include <algorithm>
#define N 200000
#define ll long long
#define ull unsigned long long
using namespace std;
void setIO(string s) {
string in=s+".in",out=s+".out";
freopen(in.c_str(),"r",stdin);
// freopen(out.c_str(),"w",stdout);
}
int cas;
multiset<ll>S;
multiset<ll>::iterator it;
ll A[N],P[N],Power[N],reward[N];
ll mult(ll x,ll y,ll mod) {
ll tmp=(long double)x/mod*y;
return ((ull)x*y-(ull)tmp*mod+mod)%mod;
}
ll qpow(ll base,ll k,ll mod) {
ll tmp=1;
for(;k;base=mult(base,base,mod),k>>=1)
if(k&1)
tmp=mult(tmp,base,mod);
return tmp;
}
ll exgcd(ll a,ll b,ll &x,ll &y) {
if(!b) {
x=1,y=0;
return a;
}
ll gcd=exgcd(b,a%b,x,y),tmp=x;
x=y,y=tmp-a/b*y;
return gcd;
}
void solve() {
S.clear();
ll ans,M,Max=0;
int i,j,n,m,flag=0,nosol=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i) scanf("%lld",&A[i]);
for(i=1;i<=n;++i) scanf("%lld",&P[i]);
for(i=1;i<=n;++i) scanf("%lld",&reward[i]);
for(i=1;i<=m;++i) scanf("%lld",&Power[i]),S.insert(Power[i]);
for(i=1;i<=n;++i) {
ll cur;
it=S.upper_bound(A[i]);
if(it!=S.begin()) it--;
cur=(*it);
S.erase(it);
S.insert(reward[i]);
Max=max(Max,A[i]%cur==0?A[i]/cur:A[i]/cur+1);
if(A[i]>P[i]) {
flag=1;
}
ll a,b,x,y,c,gcd;
a=cur,b=P[i],c=A[i];
gcd=exgcd(a,b,x,y),b=abs(b/gcd);
if(c%gcd) {
nosol=1;
break;
}
x=(mult(x,c/gcd,b)+b)%b; // 当前这局的
if(i==1) ans=x,M=b;
else {
ll curans=x,curM=b;
a=M,b=curM,c=curans-ans;
gcd=exgcd(a,b,x,y);
if(c%gcd) {
nosol=1;
break;
}
b=abs(b/gcd);
x=(mult(x,c/gcd,b)+b)%b;
ans+=M*x;
M*=curM/__gcd(M,curM);
ans=(ans%M+M)%M;
}
}
if(nosol) printf("-1
");
else printf("%lld
",flag?Max:ans);
}
int main() {
int i,j,T;
// setIO("input");
scanf("%d",&T);
for(cas=1;cas<=T;++cas)
solve();
return 0;
}