rt，WA在#3的第二个测试点

# pragma GCC optimize("Ofast,no-stack-protector")

# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

const ll inf = 1e18;

struct node {

	int x;

	ll dis;

	bool operator < (const node& t) const {

		return dis > t.dis;

	}

} ;

ll exgcd (ll a, ll b, ll& x, ll& y) {

	if (! b) {

		x = 1, y = 0;

		return a;

	}

	ll g = exgcd (b, a % b, x, y), tmp = x;

	x = y, y = tmp - a / b * y;

	return g;

}

int t, n, m, x, y;

ll h, l[100005], s[100005], dis[100005], a, b, w, ans1, ans2, g;

vector <int> v[100005];

priority_queue <node> q;

ll exg (ll a, ll b, ll c) {

	if (a < 0)
		a = -a, c = -c;

	g = exgcd (a, b, ans1, ans2);

	if (c % g)
		return inf;

	b /= g, c /= g;

	return (ans1 * c % b + b) % b;

}

ll bfs () {

	fill (dis + 2, dis + n + 1, inf);

	q.push ({1, 0});

	while (! q.empty ()) {

		node t = q.top ();
//		cout << t.x << ':' << t.dis << ' ' << (t.dis * s[t.x] + l[t.x]) % h << '\n';
		if (t.x == n) {

			while (! q.empty ())
				q.pop ();

			return t.dis;

		}

		q.pop ();

		for (int& i : v[t.x]) {

			w = exg (s[i] - s[t.x], h, t.dis * (s[t.x] - s[i]) + l[t.x] - l[i]) + 1;

			if (t.dis + w < dis[i])
				q.push ({i, dis[i] = t.dis + w});

		}

	}

	return -1;

}

int main () {

	ios::sync_with_stdio (0);

	cin.tie (0);

	cout.tie (0);

	cin >> t;

	while (t --) {

		cin >> n >> m >> h;

		for (int i = 1; i <= n; ++ i)
			cin >> l[i], v[i].clear ();

		for (int i = 1; i <= n; ++ i)
			cin >> s[i];

		while (m --) {

			cin >> x >> y;

			v[x].emplace_back (y);

			v[y].emplace_back (x);

		}

		cout << bfs () << '\n';

	}

	return 0;

}
/*
1
5 5 563619253
434499018 150448679 82645068 448213607 182107214
527639525 517489084 380964254 72412175 483680857
1 3
5 4
4 2
4 3
1 2

537455327
*/