Problem: The great hero guards the country where Homer lives. The hero has attack power A and initial health value B. There are n monsters in front of the hero. The i-th monster has attack power a_i and initial health value b_i. 

The hero or a monster is said to be living, if his or its health value is positive (greater than or equal to 1); and he or it is said to be dead, if his or its health value is non-positive (less than or equal to 0).

In order to protect people in the country, the hero will fight with monsters until either the hero is dead or all the monsters are dead.

  * In each fight, the hero can select an arbitrary living monster and fight with it. Suppose the i-th monster is selected, and the health values of the hero and the i-th monster are x and y before the fight, respectively. After the fight, the health values of the hero and the i-th monster become x-a_i and y-A, respectively. 



Note that the hero can fight the same monster more than once.

For the safety of the people in the country, please tell them whether the great hero can kill all the monsters (even if the great hero himself is dead after killing the last monster).

Input

Each test contains multiple test cases. The first line contains t (1 ≤ t ≤ 10^5) — the number of test cases. Description of the test cases follows.

The first line of each test case contains three integers A (1 ≤ A ≤ 10^6), B (1 ≤ B ≤ 10^6) and n (1 ≤ n ≤ 10^5) — the attack power of the great hero, the initial health value of the great hero, and the number of monsters.

The second line of each test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^6), where a_i denotes the attack power of the i-th monster.

The third line of each test case contains n integers b_1, b_2, ..., b_n (1 ≤ b_i ≤ 10^6), where b_i denotes the initial health value of the i-th monster.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

Output

For each test case print the answer: "YES" (without quotes) if the great hero can kill all the monsters. Otherwise, print "NO" (without quotes).

Example

Input


5
3 17 1
2
16
10 999 3
10 20 30
100 50 30
1000 1000 4
200 300 400 500
1000 1000 1000 1000
999 999 1
1000
1000
999 999 1
1000000
999


Output


YES
YES
YES
NO
YES

Note

In the first example: There will be 6 fights between the hero and the only monster. After that, the monster is dead and the health value of the hero becomes 17 - 6 × 2 = 5 > 0. So the answer is "YES", and moreover, the hero is still living.

In the second example: After all monsters are dead, the health value of the hero will become 709, regardless of the order of all fights. So the answer is "YES".

In the third example: A possible order is to fight with the 1-st, 2-nd, 3-rd and 4-th monsters. After all fights, the health value of the hero becomes -400. Unfortunately, the hero is dead, but all monsters are also dead. So the answer is "YES".

In the fourth example: The hero becomes dead but the monster is still living with health value 1000 - 999 = 1. So the answer is "NO".

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class B {

	static int n, idx;
	static int memo[][], memo2[][];
	static int max;
	static int a[];

	static int dp(int i, int l) {
		if (i == -1)
			return 0;
		if (memo[i][l] != -1)
			return memo[i][l];

		int t = 0;
		int e = dp(i - 1, l);
		if (a[i] <= l) {
			t = dp(i - 1, a[i]) + 1;
		}
		return memo[i][l] = Math.max(t, e);
	}

	static class pair implements Comparable<pair> {
		int x;
		int y;
		int idx;

		public pair(int d, int u) {
			x = d;
			y = u;
		}

		public pair(int d, int u, int idx) {
			x = d;
			y = u;
			this.idx = idx;
		}

		@Override
		public int compareTo(pair o) {
			// TODO Auto-generated method stub
			return x - o.x;
		}

		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return x + " " + y;
		}

	}

	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
//		System.out.println(Integer.MAX_VALUE);
		int t = sc.nextInt();
		while (t-- > 0) {
			int p = sc.nextInt();
			int h = sc.nextInt();
			int n = sc.nextInt();
			int[] a = new int[n];
			int[] b = new int[n];
			pair[] pa = new pair[n];
			for (int i = 0; i < b.length; i++) {
				pa[i] = new pair(sc.nextInt(), -1);
			}
			for (int i = 0; i < b.length; i++) {
				pa[i].y = sc.nextInt();
			}
			Arrays.sort(pa);
			boolean f = true;
			for (int i = 0; i < n; i++) {
				long tt = (h + pa[i].x - 1l) / pa[i].x;
				long tt2 = (pa[i].y + p - 1l) / p;
//				System.out.println(tt+" "+tt2);
				h -= tt2 * 1l * pa[i].x;
//				System.out.println(h);
				if (tt >= tt2) {
					;
				} else
					f = false;

			}
			pw.println(f ? "YES" : "NO");
		}

		pw.flush();
	}

	static class SegmentTree { // 1-based DS, OOP

		int N; // the number of elements in the array as a power of 2 (i.e. after padding)
		int[] array, sTree, lazy;

		SegmentTree(int[] in) {
			array = in;
			N = in.length - 1;
			sTree = new int[N << 1]; // no. of nodes = 2*N - 1, we add one to cross out index zero
			lazy = new int[N << 1];
			build(1, 1, N);
		}

		void build(int node, int b, int e) // O(n)
		{
			if (b == e)
				sTree[node] = array[b];
			else {
				int mid = b + e >> 1;
				build(node << 1, b, mid);
				build(node << 1 | 1, mid + 1, e);
				sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
			}
		}

		void update_point(int index, int val) // O(log n)
		{
			index += N - 1;
			sTree[index] += val;
			while (index > 1) {
				index >>= 1;
				sTree[index] = sTree[index << 1] + sTree[index << 1 | 1];
			}
		}

		void update_range(int i, int j, int val) // O(log n)
		{
			update_range(1, 1, N, i, j, val);
		}

		void update_range(int node, int b, int e, int i, int j, int val) {
			if (i > e || j < b)
				return;
			if (b >= i && e <= j) {
				sTree[node] += (e - b + 1) * val;
				lazy[node] += val;
			} else {
				int mid = b + e >> 1;
				propagate(node, b, mid, e);
				update_range(node << 1, b, mid, i, j, val);
				update_range(node << 1 | 1, mid + 1, e, i, j, val);
				sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
			}

		}

		void propagate(int node, int b, int mid, int e) {
			lazy[node << 1] += lazy[node];
			lazy[node << 1 | 1] += lazy[node];
			sTree[node << 1] += (mid - b + 1) * lazy[node];
			sTree[node << 1 | 1] += (e - mid) * lazy[node];
			lazy[node] = 0;
		}

		int query(int i, int j) {
			return query(1, 1, N, i, j);
		}

		int query(int node, int b, int e, int i, int j) // O(log n)
		{
			if (i > e || j < b)
				return 0;
			if (b >= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
			propagate(node, b, mid, e);
			int q1 = query(node << 1, b, mid, i, j);
			int q2 = query(node << 1 | 1, mid + 1, e, i, j);
			return q1 + q2;

		}

	}

	static int x, y, d;

	void extendedEuclid(int a, int b) {
		if (b == 0) {
			x = 1;
			y = 0;
			d = a;
			return;
		}
		extendedEuclid(b, a % b);
		int x1 = y;
		int y1 = x - a / b * y;
		x = x1;
		y = y1;
	}

/////////////////////////////////////////////////////////////////////////

	static long mod(long ans, int mod) {
		return (ans % mod + mod) % mod;
	}

	static long gcd(long a, long b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	static long lcm(long a, long b) {
		return (a * b) / gcd(a, b);
	}

	public static int log(int n, int base) {
		int ans = 0;
		while (n + 1 > base) {
			ans++;
			n /= base;
		}
		return ans;
	}

	static long pow(long b, long e) {
		long ans = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				ans = ((ans * 1l * b));
			e >>= 1;
			{

			}
			b = ((b * 1l * b));
		}
		return ans;
	}

	static long powmod(long r, long e, int mod) {
		long ans = 1;
		r %= mod;
		while (e > 0) {
			if ((e & 1) == 1)
				ans = (int) ((ans * 1l * r) % mod);
			e >>= 1;
			r = (int) ((r * 1l * r) % mod);
		}
		return ans;
	}

	static int ceil(int a, int b) {
		int ans = a / b;
		return a % b == 0 ? ans : ans + 1;
	}

	static long ceil(long a, long b) {
		long ans = a / b;
		return a % b == 0 ? ans : ans + 1;
	}

	static HashMap<Integer, Integer> compress(int a[]) {
		TreeSet<Integer> ts = new TreeSet<>();
		HashMap<Integer, Integer> hm = new HashMap<>();
		for (int x : a)
			ts.add(x);
		for (int x : ts) {
			hm.put(x, hm.size() + 1);
		}
		return hm;
	}

	// Returns nCr % p
	static int C[];

	static int nCrModp(int n, int r, int p) {
		if (r > n - r)
			r = n - r;
		if (C[r] != 0)
			return C[r];
		// The array C is going to store last
		// row of pascal triangle at the end.
		// And last entry of last row is nCr

		C[0] = 1; // Top row of Pascal Triangle

		// One by constructs remaining rows of Pascal
		// Triangle from top to bottom
		for (int i = 1; i <= n; i++) {

			// Fill entries of current row using previous
			// row values
			for (int j = Math.min(i, r); j > 0; j--)

				// nCj = (n-1)Cj + (n-1)C(j-1);
				C[j] = (C[j] + C[j - 1]) % p;
		}
		return C[r];
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public int[] intArr(int n) throws IOException {
			int a[] = new int[n];
			for (int i = 0; i < a.length; i++) {
				a[i] = nextInt();
			}
			return a;
		}

		public long[] longArr(int n) throws IOException {
			long a[] = new long[n];
			for (int i = 0; i < a.length; i++) {
				a[i] = nextLong();
			}
			return a;
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	public static void shuffle(int[] times2) {
		int n = times2.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = times2[i];
			times2[i] = times2[r];
			times2[r] = tmp;
		}
	}

}