题目链接：luogu4774
首先在打每一只龙的时候使用的剑是确定的，我们可以用(multiset)预处理出这些剑，定义对第(i)头龙使用的剑的攻击力为(atk_i)
当(a_i>p_i)时，根据数据范围一定有(p_i=1)，那么我们只要将每一只龙的血量减少到一个非正数，那么它在回血的时候就会达到(0)，即需要攻击它(lceilfrac{a_i}{atk_i} ceil)次即可
当(a_ileq p_i)的时候，其实我们是有了(n)个类型如下的同余方程
[atk_ixequiv a_i(mod p_i)
]
这乍一看很像CRT，但是却没有(p_i)两两互质
我们考虑直接使用扩展欧几里得求解，记前(k-1)个式子得到的某一个特解为(x)，(M=lcm(p_1,p_2,cdots,p_{k-1}))，那么前(k-1)个式子的通解可以被表示为(tM+x(tin Z))
对于第(k)个式子，有(atk_k(tM+x)equiv a_k(mod p_k))
整理得(atk_ktMequiv a_k-atk_kx(mod p_k))，求(t)
这就是裸的扩展欧几里得了，边做边维护(M)和(x)即可求解
注意一下要使用龟速乘以及一些奇奇给给的细节（见代码）
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<assert.h>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
const int N=10000;
const db pi=acos(-1.0);
//#define int long long
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,m;
ll a[1001000],atk[1001000],p[1001000],newatk[1001000];
multiset<ll> s;
multiset<ll>::iterator it;
ll read()
{
ll x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
ll mul(ll x,ll y,ll p)
{
ll ans=0;
while (y)
{
if (y&1) ans=(ans+x)%p;
x=(x+x)%p;y>>=1;
}
return ans;
}
ll gcd(ll x,ll y) {if (!y) return x;else return gcd(y,x%y);}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if (!b) {d=a;x=1;y=0;return;}
else
{
exgcd(b,a%b,d,x,y);
ll tmpx=x,tmpy=y;
x=tmpy;y=tmpx-a/b*tmpy;
}
}
void work()
{
ll x,y,d;
exgcd(atk[1],p[1],d,x,y);
if (a[1]%d) {puts("-1");return;}
ll ans=(mul(x,a[1]/d,p[1]/d)+(p[1]/d))%(p[1]/d),lcm=p[1]/d;
rep(i,2,n)
{
ll A=mul(lcm,atk[i],p[i]),B=p[i],
C=((a[i]-mul(ans,atk[i],p[i]))%p[i]+p[i])%p[i];
exgcd(A,B,d,x,y);
if (C%d) {puts("-1");return;}
x=(mul(x,C/d,B/d)+B/d)%(B/d);
ll tmplcm=lcm,d=gcd(atk[i],p[i]);
lcm=lcm/gcd(lcm,p[i]/d)*(p[i]/d);
ans=((ans+mul(x,tmplcm,lcm))%lcm+lcm)%lcm;
assert(lcm<=1e12);assert(lcm>0);
}
printf("%lld
",ans);
}
void special()
{
ll ans=0;
rep(i,1,n)
{
ll cnt=(a[i]+atk[i]-1)/atk[i];
ans=max(ans,cnt);
}
printf("%lld
",ans);
}
signed main()
{
freopen("dragon.in","r",stdin);
freopen("dragon.out","w",stdout);
int T=read();
//cout << 'a';
while (T--)
{
bool one=1;
n=read();m=read();
rep(i,1,n) a[i]=read();
rep(i,1,n) {p[i]=read();if (p[i]!=1) one=0;}
rep(i,1,n) newatk[i]=read();s.clear();
rep(i,1,m) s.insert(read());
rep(i,1,n)
{
int low=(*s.begin());
if (a[i]<low)
{
atk[i]=low;s.erase(low);
}
else
{
it=s.upper_bound(a[i]);it--;
atk[i]=(*it);s.erase(it);
}
s.insert(newatk[i]);
}
//cout << 'a';
//rep(i,1,n) cout << atk[i] << " ";cout << endl;
if (one) special();
else work();
}
return 0;
}