# 2. 题解

Emmmm… 我打同步赛的情况大概就是：看T1->哇可做赶紧写->写完了睡觉->醒来看知乎->哇还有30分钟下考没时间打暴力了->GG

• 我们武器攻击力是 $k$
• 攻击 $x$次
• 怪物回血速度为 $p$
• 回血 $y$次
• 怪物血量为 $a$

$a-kx+py=0$且要满足 $a-kx\leq 0$

$kx+py=a$（因为 $x,y$正负是随便的所以可以这样瞎 jb 变形）

• $x=x_0+q\frac{p}{gcd(p,k)}$
• $y=y_0-q\frac{k}{gcd(p,k)}$

$x\equiv x_0 \pmod{\frac{p}{gcd(p,k)}}$

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

typedef long long LL;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

LL exgcd(LL a, LL b, LL& x, LL& y)
{
if (!b) {x = 1, y = 0; return a;}
LL res = exgcd(b, a % b, y, x);
y -= a / b * x; return res;
}

LL mul(LL a, LL b, LL M)
{
a = a % M, b = b % M;
return ((a * b - (LL)(((long double) a * b + 0.5) / M) * M) % M + M) % M;
}

int T, n, m;

namespace CRT
{
LL a[NS], r[NS], mn;
void work()
{
LL A = a[1], R = r[1], x, y, g, t;
for (int i = 2; i <= n; i += 1)
{
g = exgcd(A, a[i], x, y);
if ((r[i] - R) % g) puts("-1"), exit(0);
t = a[i] / g, x = mul(x, (r[i] - R) / g % t + t, t), x = (x % t + t) % t;
R = A * x + R, A = A / g * a[i], R %= A;
}
R = (R % A + A) % A;
if (mn > R) R = R + A * ((mn - R) / A + ((mn - R) % A ? 1 : 0));
printf("%lld\n", R);
}
}

LL a[NS], p[NS], s[NS];

multiset<LL> st;

int main(int argc, char const* argv[])
{
//freopen("dragon.in", "r", stdin), freopen("dragon.out", "w", stdout);
IN(T);
while (T--)
{
IN(n), IN(m), st.clear(), CRT::mn = LLONG_MIN;
for (int i = 1; i <= n; i += 1) IN(a[i]);
for (int i = 1; i <= n; i += 1) IN(p[i]);
for (int i = 1; i <= n; i += 1) IN(s[i]);
LL tmp, x, y, g; multiset<LL>::iterator it;
for (int i = 1; i <= m; i += 1) IN(tmp), st.insert(tmp);
for (int i = 1; i <= n; i += 1)
{
it = st.upper_bound(a[i]);
if (it != st.begin()) it--, tmp = *it, st.erase(it);
else tmp = *it, st.erase(it);
CRT::mn = max(CRT::mn, a[i] / tmp + (a[i] % tmp ? 1 : 0));
st.insert(s[i]), g = exgcd(tmp, p[i], x, y), x = (x % p[i] + p[i]) % p[i];
if (a[i] % g) {puts("-1"); goto end;}
a[i] /= g, p[i] /= g, CRT::a[i] = p[i], CRT::r[i] = mul(a[i], x, p[i]);
}
CRT::work();
end : continue;
}
return 0;
}