#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main() {
    ios::sync_with_stdio(false),cin.tie(nullptr);cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, h, sum = 0;
        cin >> h >> n;

        vector<int> v(n), d(n);

        for (int i = 0; i < n; ++i) {
            cin >> v[i];
            sum += v[i];
        }
        for (int i = 0; i < n; ++i) {
            cin >> d[i];
        }

        if (sum >= h) {
            cout << 1 << '\n';
            continue;
        }

        int l = 2, r = 1e18;
        while (l < r) {
            int m = (l + r) / 2, temp = sum;

            for (int i = 0; i < n; ++i) {
                temp += (((m - 1) / d[i]) * v[i]);
            }

            if (temp < h) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        cout << l << '\n';
    }
}