#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int SIZ = 30000000 + 40;
const ll INF = 1e18;
char buf1[SIZ];
char *p1 = buf1, *p2 = buf1;
inline char readchar() {
    if (p1 == p2)
        p1 = buf1, p2 = buf1 + fread(buf1, 1, SIZ, stdin);
    return p1 == p2 ? EOF : *p1++;
}
int read() {
    int ret, c;
    while ((c = readchar()) > '9' || c < '0')
        ;
    ret = c - '0';
    while ((c = readchar()) >= '0' && c <= '9')
        ret = ret * 10 + c - '0';
    return ret;
}

const int N = 1e6 + 60;

int n, m;
ll K;
int a[N];
ll cost[N];
vector<int> div2[N];
ll dp[N];

void init() {
    for (int i = 1; i <= 1000000; i++) {
        for (int j = i; j <= 1000000; j += i)
            div2[j].push_back(i);
    }
}

ll mn;

void prep() {
    for (int i = 1; i <= m; i++)
        dp[i] = cost[i];
    for (int i = 1; i <= m; i++)
        for (auto &d : div2[i]) {
            dp[i] = min(dp[i], dp[d] + dp[i / d]);
        }
    // for(int i = 1; i <= m; i++)
    //     cout << dp[i] << " ";
    // cout << "\n===\n";
    dp[m + 1] = INF;
    for (int i = m - 1; i >= 1; i--)
        dp[i] = min(dp[i], dp[i + 1]);
    mn = INF;
    for (int i = 1; i <= m; i++) {
        ll y = (m + 1 + i - 1) / i;
        // cout << i << " " << y << " | " << dp[i] + dp[y] <<"\n";
        mn = min(mn, dp[i] + dp[y]);
    }
    // cout << mn << endl;
    dp[m + 1] = mn;
    for (int i = m; i >= 1; i--)
        dp[i] = min(dp[i], dp[i + 1]);
}

bool check(int mid) {
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        cnt += (a[i] <= mid);
    if (cnt * 2 >= n)
        return true;
    ll total = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > mid) {
            int x = (mid == 0 ? a[i] + 1 : (a[i] + mid - 1) / mid);
            ll now = dp[x];
            if (now + total <= K)
                total += now, cnt++;
        }
        if (cnt * 2 >= n)
            return true;
    }
    return false;
}

void solve() {
    n = read(), m = read(), K = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= m; i++)
        cost[i] = read();
    prep();

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

int main() {
    init();
    int T = read();
    while (T--)
        solve();
    return 0;
}