#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstdint>
#include <iostream>
#include <set>
#include <numeric>
#include <queue>
#include <map>
#include <iomanip>
#include <sstream>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

struct DayPeriodDamage {
    int64_t day;
    int64_t period;
    int64_t damage;
};

bool operator<(const DayPeriodDamage& lhs, const DayPeriodDamage& rhs){
    if (lhs.day != rhs.day) return lhs.day > rhs.day;
    if (lhs.damage != rhs.damage) return lhs.damage < rhs.damage;
    return lhs.period > rhs.period;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int64_t health, attacks_count;
        cin >> health >> attacks_count;
        vector<int64_t> attacks_powers(attacks_count);
        for (int64_t& power : attacks_powers) cin >> power;
        vector<int64_t> refresh_duration(attacks_count);
        for (int64_t& time : refresh_duration) cin >> time;

        priority_queue<DayPeriodDamage> pq;
        for (int i = 0; i < attacks_count; ++i) {
            pq.push({ 1, refresh_duration[i], attacks_powers[i] });
        }

        while (health > 0) {
            auto [day, period, damage] = pq.top();
            pq.pop();

            health -= damage;
            if (health <= 0) {
                cout << day << '\n';
                break;
            }

            pq.push({ day + period, period, damage });
        }
    }

    return 0;
}