#include<bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(),(a).end()
using namespace std;

#define int ll
const int N = 1e6 + 10;

int n, m, k;
int a[N], cost[N];
vector<int> v[N];

vector<int> isprime(N), prime;
void sieve()
{
    for(int i = 2; i < N; i++) isprime[i] = 1;
    for(int i = 2; i < N; i++)
    {
        if(isprime[i]) prime.push_back(i);
        for(int &it : prime)
        {
            if(i * it >= N) break;
            isprime[i * it] = 0;
            if(i % it == 0) break;
        }
    }
}
void get(int x)
{
    int now = x;
    for(auto &it : prime)
    {
        if(it * it > x) break;
        if(x % it == 0) v[now].push_back(it);
        while(x % it == 0) x /= it;
    }
    if(x > 1) v[now].push_back(x);
}
void init()
{
    sieve();
    for(int i = 2; i < N; i++) get(i);
}

int mi[21][N], Log[N];
void init_ST()
{
    for(int i = 1; i <= m; i++) mi[0][i] = cost[i];
    for(int j = 1; j <= 20; j++)
        for(int i = 1; i + (1 << j) - 1 <= m; i++)
            mi[j][i] = min(mi[j - 1][i], mi[j - 1][i + (1 << (j - 1))]);
    Log[1] = 0;
    for(int i = 2; i <= m; i++) Log[i] = Log[i / 2] + 1;
}

int query(int l, int r)
{
    int k = Log[r - l + 1];
    return min(mi[k][l], mi[k][r - (1 << k) + 1]);
}

bool check(int x)
{
    int res = 0;
    for(int i = 1; i <= n / 2 + 1; i++) 
    {
        if(a[i] > x)
        {
            int L, R = a[i];
            int l = 2, r = a[i];
            while(l <= r)
            {
                int mid = (l + r) / 2;
                if(a[i] / mid <= x) r = mid - 1, L = mid;
                else l = mid + 1;
            }
            res += query(L, R);
        }

        if(res > k) return 0;
    }
    return 1;
}

void solve()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> cost[i];

    sort(a + 1, a + 1 + n);

    for(int i = 2; i <= m; i++)
    {
        for(int j = 2; j * j <= i; j++)
        {
            if(i % j == 0) cost[i] = min(cost[i], cost[j] + cost[i / j]);
        }
    }
    // for(int i = 2; i <= m; i++) for(auto &it : v[i]) cost[i] = min(cost[i], cost[it] + cost[i / it]);

    init_ST();

    int l = 0, r = a[n / 2 + 1];
    int ans = r;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }

    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    
    // init();

    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}