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 Main {
    static void solve() {
        int t = ni();
        for(int i=0;i<t;i++) testCase();
    }	
    
    static void testCase() {
        long A = ni(), B = ni();
        int N = ni();
        var a = nla(N);
        var b = nla(N);
        var c = new long[N];
        for(int i=0;i<N;i++){
            c[i] = (b[i] + A - 1) / A * a[i];
        }
        long max = 0;
        int maxId = 0;
        for(int i=0;i<N;i++){
            if(max < a[i]) {
                max = a[i];
                maxId = i;
            }
        }
        
        for(int i=0;i<N;i++){
            if(i == maxId) continue;
            B -= c[i];
        }
        B -= ((b[maxId] + A - 1) / A - 1) * a[maxId];
        if(B <= 0) {
            out.println("NO");
            return;
        }
        out.println("YES");
        
        
    }	
    
    //constants
    static final int inf = Integer.MAX_VALUE / 2;
    static final long linf = Long.MAX_VALUE / 3;
    static final double dinf = Double.MAX_VALUE / 3;
    static final long mod = (long) 1e9 + 7;
    static final int[] dx = { -1, 0, 1, 0 }, dy = { 0, -1, 0, 1 }, dx8 = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy8 = { -1, 0, 1, -1, 1, -1, 0, 1 };
    static final double eps = 1e-10;
    
    //libraries		
    static long[] cum(int a[]) {
        long[] cum = new long[a.length + 1];
        for(int i=0;i<a.length;i++) cum[i+1] = cum[i] + a[i];
        return cum;
    }
    static long[] cum(long a[]) {
        long[] cum = new long[a.length + 1];
        for(int i=0;i<a.length;i++) cum[i+1] = cum[i] + a[i];
        return cum;
    }
    static void reverse(int ar[]) {
        int len = ar.length;
        for (int i = 0; i < len / 2; i++) {
            int t = ar[i];
            ar[i] = ar[len - 1 - i];
            ar[len - 1 - i] = t;
        }
    }
    static void reverse(long ar[]) {
        int len = ar.length;
        for (int i = 0; i < len / 2; i++) {
            long t = ar[i];
            ar[i] = ar[len - 1 - i];
            ar[len - 1 - i] = t;
        }
    }
    static void reverse(double ar[]) {
        int len = ar.length;
        for (int i = 0; i < len / 2; i++) {
            double t = ar[i];
            ar[i] = ar[len - 1 - i];
            ar[len - 1 - i] = t;
        }
    }
    static void reverse(char ar[]) {
        int len = ar.length;
        for (int i = 0; i < len / 2; i++) {
            char t = ar[i];
            ar[i] = ar[len - 1 - i];
            ar[len - 1 - i] = t;
        }
    }
    static String getReverse(String s) {
        StringBuilder sb = new StringBuilder(s);
        return sb.reverse().toString();
    }
    static <T> void reverse(T[] ar) {
        int len = ar.length;
        for (int i = 0; i < len / 2; i++) {
            T t = ar[i];
            ar[i] = ar[len - 1 - i];
            ar[len - 1 - i] = t;
        }
    }
    static int[] concat(int x, int arr[]) {
        int ret[] = new int[arr.length + 1];
        System.arraycopy(arr, 0, ret, 1, ret.length - 1);
        ret[0] = x;
        return ret;
    }
    static int[] concat(int arr[], int x) {
        int ret[] = new int[arr.length + 1];
        System.arraycopy(arr, 0, ret, 0, ret.length - 1);
        ret[ret.length - 1] = x;
        return ret;
    }
    static long[] concat(long x, long arr[]) {
        long ret[] = new long[arr.length + 1];
        System.arraycopy(arr, 0, ret, 1, ret.length - 1);
        ret[0] = x;
        return ret;
    }
    static long[] concat(long arr[], long x) {
        long ret[] = new long[arr.length + 1];
        System.arraycopy(arr, 0, ret, 0, ret.length - 1);
        ret[ret.length - 1] = x;
        return ret;
    }
    static char[] concat(char x, char arr[]) {
        char ret[] = new char[arr.length + 1];
        System.arraycopy(arr, 0, ret, 0, ret.length - 1);
        ret[ret.length - 1] = x;
        return ret;
    }
    static char[] concat(char arr[], char x) {
        char ret[] = new char[arr.length + 1];
        System.arraycopy(arr, 0, ret, 0, ret.length - 1);
        ret[ret.length - 1] = x;
        return ret;
    }
    static int max(int x, int y) {
        return Math.max(x, y);
    }
    static int min(int x, int y) {
        return Math.min(x, y);
    }
    static int max(int x, int y, int z) {
        x = Math.max(x, y);
        x = Math.max(x, z);
        return x;
    }
    static int min(int x, int y, int z) {
        x = Math.min(x, y);
        x = Math.min(x, z);
        return x;
    }
    static long max(long x, long y) {
        return Math.max(x, y);
    }
    static long min(long x, long y) {
        return Math.min(x, y);
    }
    static long max(long x, long y, long z) {
        x = Math.max(x, y);
        x = Math.max(x, z);
        return x;
    }
    static long min(long x, long y, long z) {
        x = Math.min(x, y);
        x = Math.min(x, z);
        return x;
    }
    static double max(double x, double y) {
        return Math.max(x, y);
    }
    static double min(double x, double y) {
        return Math.min(x, y);
    }
    static double max(double x, double y, double z) {
        x = Math.max(x, y);
        x = Math.max(x, z);
        return x;
    }
    static double min(double x, double y, double z) {
        x = Math.min(x, y);
        x = Math.min(x, z);
        return x;
    }
    static void sort(int[] ar) {
        Arrays.sort(ar);
    }
    static void sort(long[] ar) {
        Arrays.sort(ar);
    }
    static void sort(double[] ar) {
        Arrays.sort(ar);
    }
    static void sort(char[] ar) {
        Arrays.sort(ar);
    }
    static void rsort(int[] ar) {
        Arrays.sort(ar);
        int len = ar.length;
        for (int i = 0; i < len / 2; i++) {
            int tmp = ar[i];
            ar[i] = ar[len - 1 - i];
            ar[len - 1 - i] = tmp;
        }
    }
    static void rsort(long[] ar) {
        Arrays.sort(ar);
        int len = ar.length;
        for (int i = 0; i < len / 2; i++) {
            long tmp = ar[i];
            ar[i] = ar[len - 1 - i];
            ar[len - 1 - i] = tmp;
        }
    }
    static void rsort(double[] ar) {
        Arrays.sort(ar);
        int len = ar.length;
        for (int i = 0; i < len / 2; i++) {
            double tmp = ar[i];
            ar[i] = ar[len - 1 - i];
            ar[len - 1 - i] = tmp;
        }
    }
    static void rsort(char[] ar) {
        Arrays.sort(ar);
        int len = ar.length;
        for (int i = 0; i < len / 2; i++) {
            char tmp = ar[i];
            ar[i] = ar[len - 1 - i];
            ar[len - 1 - i] = tmp;
        }
    }
    static void fill(int arr[], int x) {
        Arrays.fill(arr, x);
    }
    static void fill(long arr[], long x) {
        Arrays.fill(arr, x);
    }
    static void fill(boolean arr[], boolean x) {
        Arrays.fill(arr, x);
    }
    static void fill(double arr[], double x) {
        Arrays.fill(arr, x);
    }
    static void fill(int arr[][], int x) {
        for (int i = 0; i < arr.length; i++)
            Arrays.fill(arr[i], x);
    }
    static void fill(long arr[][], long x) {
        for (int i = 0; i < arr.length; i++)
            Arrays.fill(arr[i], x);
    }
    static void fill(double arr[][], double x) {
        for (int i = 0; i < arr.length; i++)
            Arrays.fill(arr[i], x);
    }
    static void fill(boolean arr[][], boolean x) {
        for (int i = 0; i < arr.length; i++)
            Arrays.fill(arr[i], x);
    }
    //MOD culc
    static long plus(long x, long y) {
        long res = x + y;
        return res >= mod ? res - mod : res;
    }
    static long sub(long x, long y) {
        long res = x - y;
        return res < 0 ? res + mod : res;
    }
    static long mul(long x, long y) {
        return x * y % mod;
    }
    static long div(long x, long y) {
        return x * pow(y, mod - 2) % mod;
    }
    static long pow(long x, long y) {
        if (y < 0) return 0;
        if (y == 0) return 1;
        if (y % 2 == 1) return (x * pow(x, y - 1)) % mod;
        long root = pow(x, y / 2);
        return root * root % mod;
    }
    public static void main(String[] args) throws Exception {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        solve();
        out.flush();
    }
    //input
    static InputStream is;
    static PrintWriter out;
    static String INPUT = "";
    private static byte[] inbuf = new byte[1024];
    static int lenbuf = 0, ptrbuf = 0;
    private static int readByte() {
        if (lenbuf == -1)
            throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0)
                return -1;
        }
        return inbuf[ptrbuf++];
    }
    private static boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }
    private static int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b));
        return b;
    }
    @SuppressWarnings("unused")
    private static double nd() {
        return Double.parseDouble(ns());
    }
    @SuppressWarnings("unused")
    private static char nc() {
        return (char) skip();
    }
    private static String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    private static char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    @SuppressWarnings("unused")
    private static char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for (int i = 0; i < n; i++)
            map[i] = ns(m);
        return map;
    }
    @SuppressWarnings("unused")
    private static int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = ni();
        return a;
    }
    @SuppressWarnings("unused")
    private static long[] nla(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nl();
        return a;
    }
    @SuppressWarnings("unused")
    private static int[][] na(int n, int m){
        int[][] res = new int[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                res[i][j] = ni();
            }
        }
        return res;
    }
    @SuppressWarnings("unused")
    private static long[][] nla(int n, int m){
        long[][] res = new long[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                res[i][j] = nl();
            }
        }
        return res;
    }
    private static int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
            ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        
        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    private static long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
            ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        
        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
}