#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

typedef long long ll;
typedef pair<int, int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
std::ostream& operator << (std::ostream& os, const vector<T>& a) {
    for (const T& x : a) {
        os << x << ' ';
    }
    return os;
}

const int M = 1e6 + 6;

vector<int> divs[M + 1];

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(all(a));
    vector<int> cost(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> cost[i];
    }
    cost[1] = 0;
    for (int t = 0; t < 5; ++t) {
        for (int i = 1; i <= m; ++i) {
            for (int j : divs[i]) {
                cost[i] = min(cost[i], cost[j] + cost[i / j]);
            }
            if (i > 1) {
                int j = m / i + 1;
                cost[m] = min(cost[m], cost[i] + cost[j]);
            }
        }
        for (int i = m - 1; i >= 1; --i) {
            cost[i] = min(cost[i], cost[i + 1]);
        }
    }

    auto check = [&](int x) {
        ll sum = 0;
        for (int i = 0; i <= n / 2; ++i) {
            int y = a[i] / x + 1;
            sum += cost[y];
        }
        return sum <= k;
    };

    int low = 0, high = m + 1;
    while (high - low > 1) {
        int mid = (low + high) / 2;
        if (check(mid)) {
            high = mid;
        } else {
            low = mid;
        }
    }
    cout << low << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 2; i <= M; ++i) {
        for (int j = 2 * i; j <= M; j += i) {
            divs[j].push_back(i);
        }
    }

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}