记录编号	608354	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2975.[NOI 2018]屠龙勇士	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	7.580 s
提交时间	2025-10-25 10:18:24	内存使用	12.29 MiB

#include <cstdio>
#define isdigit(ch) (ch >= '0' && ch <= '9')

template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T> void write(T x) {
  if (x < 0) x = -x, putchar('-');
  int sta[sizeof(T) << 2], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while (x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar('\n');
}

#include <set>
#define max(__a, __b) [](i128 _a, i128 _b) {return _a > _b ? _a : _b;}(__a, __b)
typedef __int128 i128;

i128 GCD(i128 x, i128 y) {
  return y == 0 ? x : GCD(y, x % y);
}

i128 LCM(i128 x, i128 y) {
  return x / GCD(x, y) * y;
}

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

i128 inverse(i128 a, i128 mod) {
  i128 x, y;
  EXGCD(a, mod, x, y);
  return (x % mod + mod) % mod;
}

const int MAXN = 1e5 + 10;

int n, m;
i128 a[MAXN], r[MAXN], p[MAXN];

i128 EXCRT(i128 maxx) {
  i128 ans = r[1], M = p[1];
  for (int i = 2; i <= n; ++i) {
    i128 t, y, d = EXGCD(M, p[i], t, y), c = ((r[i] - ans) % p[i] + p[i]) % p[i];
    if (c % d) return -1;
    t = t * (c / d);
    ans = ans + t * M;
    M = LCM(M, p[i]);
    ans = (ans % M + M) % M;
  }
  if (ans < maxx) while(ans < maxx) ans += M;
  return ans;
}

i128 health[MAXN], heal[MAXN], reward[MAXN], attack[MAXN], d[MAXN];

void work() {
  ::std::multiset<i128> s;
  n = read<int>(), m = read<int>();
  for (int i = 1; i <= n; ++i) {
    health[i] = read<i128>();
  }
  for (int i = 1; i <= n; ++i) {
    heal[i] = read<i128>();
  }
  for (int i = 1; i <= n; ++i) {
    reward[i] = read<i128>();
  }
  for (int i = 1; i <= m; ++i) {
    attack[i] = read<i128>();
    s.insert(attack[i]);
  }

  i128 maxx = 0;
  for (int i = 1; i <= n; ++i) {
    ::std::multiset<i128>::iterator it = s.upper_bound(health[i]);
    if (it != s.begin()) it--;
    a[i] = *it, r[i] = health[i], p[i] = heal[i];
    s.erase(it), s.insert(reward[i]);

    d[i] = GCD(a[i], p[i]);
    if (r[i] % d[i]) {
      write(-1);
      return ;
    }

    maxx = max(maxx, (r[i] + a[i] - 1) / a[i]);
    a[i] /= d[i], r[i] /= d[i], p[i] /= d[i];
    r[i] = r[i] * inverse(a[i], p[i]) % p[i];
  }

  write(EXCRT(maxx));
}

int T;

int main() {
  T = read<int>();
  while (T--) {
    work();
  }
  return 0;
}