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

#include <cstdio>
#include <set>
#define isdigit(ch) ((ch) >= '0' && (ch) <= '9')
#define max(__a, __b) [&](int128 _a, int128 _b) {return _a > _b ? _a : _b;} ((__a), (__b))
typedef long long ll;
typedef __int128 int128;

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, char ed = '\n') {
  if (x < 0) putchar('-'), x = -x;
  static int sta[128], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while(x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}

int128 gcd(int128 x, int128 y) {
  return y == 0 ? x : gcd(y, x % y);
}

int128 lcm(int128 x, int128 y) {
  return x / gcd(x, y) * y;
}

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

int128 inverse(int128 a, int128 mod) {
  int128 x, y;
  exgcd(a, mod, x, y);
  return (x % mod + mod) % mod;
}

const int MAXN = 1e5 + 10;

int n, m;
int128 a[MAXN], r[MAXN], p[MAXN], d[MAXN];

int128 EXCRT(int128 maxx) {
  int128 ans = r[1], M = p[1];
  for (int i = 2; i <= n; ++i) {
    int128 t, y, d = exgcd(M, p[i], t, y), c = ((r[i] - ans) % p[i] + p[i]) % p[i];
    if (c % d != 0) 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;
}

int128 health[MAXN];
int128 heal[MAXN];
int128 reward[MAXN];
int128 atack[MAXN];

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

  int128 maxx = 0;
  for (int i = 1; i <= n; ++i) {
    ::std::multiset <int128> :: 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] != 0) {
      write(-1);
      return ;
    }
    maxx = max(maxx, (r[i] + a[i] - 1) / a[i]);

    a[i] /= d[i], p[i] /= d[i], r[i] /= d[i];
    r[i] = r[i] * inverse(a[i], p[i]) % p[i];
    //printf("x = %lld (mod %lld)\n", r[i], p[i]);
  }

  write(EXCRT(maxx));
}

int main() {
  freopen("2018dragon.in", "r", stdin);
  freopen("2018dragon.out", "w", stdout);
  int T = read<int>();
  while (T--) {
    work();
  }
  return 0;
}