[NOI2018]屠龙勇士

待补题解。

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>


using namespace std;
typedef long long ll;
#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

ll chkmax(ll &a,ll b){return a = a>b?a:b;}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> VI;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();ll f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
	read(first);
	read(args...);
}

ll euclid(ll a, ll b, ll &x, ll &y) {
	if (b) { ll d = euclid(b, a % b, y, x);
		return y -= a/b * x, d; }
	return x = 1, y = 0, a;
}

__int128_t crt(__int128_t a, __int128_t m, __int128_t b, __int128_t n) {
	if (n > m) swap(a, b), swap(m, n);
	ll cx,cy,g = euclid(m, n, cx, cy);
	__int128_t x = cx,y = cy;
	if(!((a - b) % g == 0))return -1;
	x = (b - a) % n * x % n / g * m + a;
	return x < 0 ? x + m*n/g : x;
}

ll mul(ll a,ll b,ll c){
	return (ll)(__int128_t(a)*b%c);
}
ll T;
int main() {
	read(T);
	while(T--){
		int n,m;
		ll cu,lwb = 0,ma,mm;
		multiset<ll> Se;
		read(n,m);
		vector<ll> a(n+1),p(n+1),aw(n+1),u(n+1),req(n+1),md(n+1);
		for(int i=1;i<=n;i++)read(a[i]);
		for(int i=1;i<=n;i++)read(p[i]);
		for(int i=1;i<=n;i++)read(aw[i]);
		for(int i=1;i<=m;i++){
			read(cu);
			Se.insert(cu);
		}
		for(int i=1;i<=n;i++){
			auto it = Se.upper_bound(a[i]);
			if(*it != *Se.begin())it--;
			u[i] = *it;
			Se.erase(Se.find(*it));
			Se.insert(aw[i]);
		}
		for(int i=1;i<=n;i++){
			lwb = max(lwb,(a[i]+u[i]-1)/u[i]);
			ll x,y,d = euclid(u[i]%p[i],p[i],x,y),cr = a[i]%p[i];
			if(cr%d == 0){
				md[i] = p[i]/d;
				x = (x%md[i])+md[i];
				req[i] = mul(x,cr/d,md[i]);
			}else goto fail;
		}
		ma = 0;
		mm = 1;
		for(int i=1;i<=n;i++){
			ma = crt(ma,mm,req[i],md[i]);
			if(ma == -1){
				goto fail;
			}
			mm = mm*(md[i]/__gcd(mm,md[i]));
		}
		cout<<mm*((lwb-ma+mm-1)/mm)+ma<<endl;
		continue;
		fail:;
		cout<<-1<<endl;
	}
	return 0;
}