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:
//package CodeForces;

import java.io.*;
import java.util.*;
import javafx.util.Pair;

public class Main {

    public static MyScanner sc = new MyScanner();
    public static int MOD = 1000000007;
    // __builtin_popcountll(n) <-- c++ // binary count(1) ex. 8 --> 0100 --> 1
    HashSet<Integer> set = new HashSet<>();
    HashMap<Integer, Integer> map = new HashMap<>();
    Random r = new Random();
    ArrayList<Integer> l = new ArrayList<>();
    LinkedList<Integer> link = new LinkedList<>();
    public static int[][] dp;

    /* ********************************* main ********************************* */
    public static void main(String[] args) {
        int t = 1;
        t = sc.nextInt();
        while(t-- > 0){
            int A = sc.nextInt();
            int B = sc.nextInt();
            int n = sc.nextInt();
            ArrayList<MyPair> l = new ArrayList<>();
            for (int i = 0; i < n; i++)
                l.add(new MyPair(sc.nextInt(), 0));
            for (int i = 0; i < n; i++)
                l.get(i).y = sc.nextInt();
            Collections.sort(l, (o1, o2) -> { return o1.x - o2.x; });
            boolean ok = false;
            for (int i = 0; i < n; i++) {
                if(B < 1){
                    ok = true;
                    break;
                } else {
                    B -= l.get(i).x;
                    l.get(i).y -=  A;
                    if(l.get(i).y >= 1) --i;
                }
            }
            System.out.println(ok ? "NO" : "YES");
        }
    }
    /* ********************************* End ********************************* */
    
    public static void QuickSort(int[] a){
        QuickSort(a, 0, a.length - 1);
    }
    
    public static void QuickSort(int[] a, int f, int l){
        if(l > f){
            int pivotIndex = partition(a, f, l);
            System.out.println(Arrays.toString(a));
            QuickSort(a, f, pivotIndex - 1);
            System.out.println(Arrays.toString(a));
            QuickSort(a, pivotIndex + 1, l);
            System.out.println(Arrays.toString(a));
        }
    }
    public static int partition(int[] a, int f, int l){
        int pivot = a[l];
        int low = f;
        int high = l - 1;
        
        while(high > low){
            while(low <= high && a[low] <= pivot)
                low++;
            while(low <= high && a[high] > pivot)
                high--;
            if(high > low){
                int temp = a[high];
                a[high] = a[low];
                a[low] = temp;
            }
        }
        
        while(high > f && a[high] >= pivot)
            high--;
        
        if(pivot > a[high]){
            a[l] = a[high];
            a[high] = pivot;
            return high;
        }
        else{
            return l;
        }
        // Worst-Case O(n^2)
        // Best-Case O(n)
        // Average-Case O(n log(n))
    }
    
    public static void bucketSort(int a[], int n) { 
        if (n <= 0) 
            return; 
  
        ArrayList<Integer>[] buckets = new ArrayList[n]; 
  
        for (int i = 0; i < n; i++) { 
            buckets[i] = new ArrayList<Integer>(); 
        } 
  
        for (int i = 0; i < n; i++) { 
            double idx = a[i] * 0.01; 
            buckets[(int)idx].add(a[i]); 
        } 
        
        
        for (int i = 0; i < a.length - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < a.length; j++)
                if(a[j] < a[min_idx])
                    min_idx = j;
            int temp = a[min_idx];
            a[min_idx] = a[i];
            a[i] = temp;
        }
  
        int index = 0; 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < buckets[i].size(); j++) { 
                a[index++] = buckets[i].get(j); 
            } 
        } 
    } 
     
    public static void InsertionSort(int[] a){
        for (int i = 1; i < a.length; i++) {
            int temp = a[i], k;
            for (k = i - 1; k >= 0 && a[k] > temp; k--)
                a[k+1] = a[k];
            a[k+1] = temp;
            System.out.println(Arrays.toString(a));
        }
        // time complexity O(n^2)
    }
        
    public static ArrayList<Integer> factorize(Long n){
        HashSet<Integer> set = new HashSet<>();
        while(n%2 == 0){
            set.add(2);
            n /= 2;
        }
        for (int i = 3; i <= Math.sqrt(n); i = i + 2) {
            while (n % i == 0) {
                set.add(i);
                n /= i;
            }
        }
        ArrayList<Integer> l = new ArrayList<>(set);
        return l;
    }
    
    public static boolean contain(Queue q1, Queue q2, int i){
        return containQ1(q1, q2, q1.size() - 1) && containQ2(q2, q1, q2.size() - 1);
    }
    
    public static boolean containQ1(Queue q1, Queue q2, int i){
        if(i == -1) return true;
        if(q2.contains(q1.peek())){
            q1.add(q1.remove()); 
            return containQ1(q1, q2, i - 1);
        }
        return false;
    }
    
    public static boolean containQ2(Queue q1, Queue q2, int i){
        if(i == -1) return true;
        if(q2.contains(q1.peek())){
            q1.add(q1.remove()); 
            return containQ2(q1, q2, i - 1);
        }
        return false;
    }
    
    public static <E> void HeapSort(E[] a){
        HeapSort(a, (e1, e2) -> ((Comparable<E>)e1).compareTo(e2));
    }
    
    public static <E> void HeapSort(E[] a, Comparator<E> c){
//        Heap<E> heap = new Heap<>(c);
//        for (int i = 0; i < a.length; i++) heap.add(a[i]);
//        for (int i = a.length - 1; i >= 0; i--) a[i] = heap.remove();
    }
    

    
    public static void MergeSort(int[] a){
        if(a.length > 1){
            int firstHalf_len = a.length / 2;
            int[] firstHalf = new int[firstHalf_len];
            System.arraycopy(a, 0, firstHalf, 0, firstHalf_len);
            MergeSort(firstHalf);
            
            int secondHalf_len = a.length - firstHalf_len;
            int[] secondHalf = new int[secondHalf_len];
            System.arraycopy(a, firstHalf_len, secondHalf, 0, secondHalf_len);
            MergeSort(secondHalf);
            
            Merge(firstHalf, secondHalf, a);
        }
        // O(n log(n)) ... splits O(log n) ,, copy O(n)
        // O(n log(n)) ... merges the subarrays O(log n) ,, N of times 
        // total time complexity merge sort O(n log(n))
    }
    
    public static void Merge(int[] a, int[] b, int[] temp){
        int curr1 = 0; // current index in a
        int curr2 = 0; // current index in b
        int curr3 = 0; // current index in temp
        
        while(curr1 < a.length && curr2 < b.length){
            if(a[curr1] < b[curr2])
                temp[curr3++] = a[curr1++];
            else
                temp[curr3++] = b[curr2++]; 
        }
        
        while(curr1 < a.length)
            temp[curr3++] = a[curr1++];
        
        while(curr2 < b.length)
            temp[curr3++] = b[curr2++];
    }
    
    public static void SelectionSort(int[] a){
        for (int i = 0; i < a.length - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < a.length; j++)
                if(a[j] < a[min_idx])
                    min_idx = j;
            int temp = a[min_idx];
            a[min_idx] = a[i];
            a[i] = temp;
        }
        // time complexity O(n^2)
    }
        
    public static void BubbleSort(int[] a){
        boolean needNextPass = true;
        for (int i = 1; i < a.length && needNextPass; i++) {
            needNextPass = false;
            for (int j = 0; j < a.length - i; j++) {
                if(a[j] > a[j+1]){
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                    needNextPass = true;
                }
            }
        }
        // Worst-Case time complexity O(n^2)
    }
    
    public static int BinarySearch(int[] a, int v, int f, int l){
        if(f > l) return -1;
        int mid = (f + l)/2;
        if(a[mid] == v)
            return mid;
        if(v < a[mid])
            return BinarySearch(a, v, f, mid - 1);
        else
            return BinarySearch(a, v, mid + 1, l);
    }
    

    public static long gcd(long m, long n){
        return n != 0 ? gcd(n, m%n) : n;
    }
    
    public static class MyScanner {

        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static class MyPair {

        int x;
        int y;

        public MyPair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public String toString() {
            return "[" + x  + ", " + y + "]";
        }
        
    }

    public static int Fibonacci(int n) {
        int[] a = new int[n + 1];
        a[0] = 0;
        a[1] = 1;
        for (int i = 2; i < a.length; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }
        return a[n];
    }

    public static boolean isprime(long n) {
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static int[] addarr(int[] a, int n) {
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        return a;
    }

    public static long factt(long n) {
        if (n == 0) {
            return 1;
        }
        return n * factt(n - 1);
    }

    public static long sumDigit(long n) {
        int a = 0;
        while (n != 0) {
            a += n % 10;
            n /= 10;
        }
        return a;
    }

    public static long pow(long n, long p) {
        return p == 0 ? 1 : n * pow(n, p - 1);
    }

    public static long fastpow(long v, long p) {
        if (p == 0) {
            return 1;
        }
        if (p == 1) {
            return v;
        }
        long ans = fastpow(v, p / 2);
        if (p % 2 == 1) {
            return ans * ans * v;
        } else {
            return ans * ans;
        }
    }
    
    public static int LCS(String s1, String s2, int i, int j) {
        if (i == -1 || j == -1) {
            return 0;
        } else if (dp[i][j] != 0) {
            return dp[i][j];
        } else if (s1.charAt(i) == s2.charAt(j)) {
            return dp[i][j] = 1 + LCS(s1, s2, i - 1, j - 1);
        } else {
            return dp[i][j] = Math.max(LCS(s1, s2, i - 1, j), LCS(s1, s2, i, j - 1));
        }
    }

}