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

typedef long long ll;

// #define tpyeinput int
// inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
// inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}

template<typename T>
void read(T &x) {
    int f = 1;
    x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
}

const int N = 1e6+10;

int n, m, K;
int a[N], f[N][30];
int M[N];

void ST_pre() {
    for(int i=1; i<=m; i++) f[i][0] = M[i];
    int t = log(m)/ log(2) + 1;
    for(int j=1; j<t; j++) {
        for(int i=1; i<=m-(1<<j)+1; i++) {
            f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);
        }
    }
}

int query(int l, int r) {
    int k = log(r-l+1)/log(2);
    return min(f[l][k], f[r-(1<<k)+1][k]);
}

int ksm(int x,int y)
{
    int res = 1;
    while(y)
    {
        if(y & 1)
        {
            res *= x;
        }
        x *= x;
        y >>= 1;
    }
    return res;
}

void precost()
{
    for(int i = 4; i <= m; i++)
    {
        int mn = M[i];
        vector<pair<int,int>> prims;
        int ii = i;
        for(int j = 2; j <= sqrt(i); j++)
        {
            if(ii % j == 0)
            {
                prims.push_back({j,0});
                while(ii % j == 0)
                {
                    prims.back().second++;
                    ii /= j;
                }
            }
        }
        if(ii > 1)
        {
            prims.push_back({i,1});
        }
        if(prims.size() == 1)
        {
            auto [x,y] = prims[0];
            for(int j = 1; j <= (y >> 1); j++)
            {
                mn = min(mn, M[ksm(x,j)] + M[ksm(x,y-j)]);
            }
        }else
        {
            int sum = 0;
            for(auto [x,y] : prims)
            {
                sum += M[ksm(x,y)];
            }
            mn = min(mn, sum);
        }
        M[i] = mn;
    }
}


ll check(int mid) {
    if(mid == a[n/2+1]) return 0;
    if(mid > a[n/2+1]) return -1;
    ll cost = 0;
    int l = lower_bound(a+1, a+1+n, mid+1) - a;
    // int ll = lower_bound(a+1, a+1+n, mid) - a;
    int cnt = l-1;
    // if(cntt > n/2) return -1;
    while(cnt < n/2+1) {
        int tmp = mid ? (a[l]-1)/mid+1 : a[l]+1;
        cost += query(tmp, m);
        cnt++; l++;
    }
    return cost;
}

void solve() {
    read(n);  read(m); read(K);

    for(int i=1; i<=n; i++) read(a[i]);
    for(int i=1; i<=m; i++) read(M[i]);

    // M_pre();
    precost();

    ST_pre();
    sort(a+1, a+1+n);
    int l = 0, r = a[n/2+1];
    while(l < r) {
        int mid = l + r >> 1;
        ll cost = check(mid);
        if(cost >= 0 && cost <= K) r = mid;
        else l = mid + 1;
    }
    printf("%lld\n", l);
}

signed main() {
#ifdef LOCAL_TEST
    freopen("test.in", "r", stdin);
#endif
    int times = 1;
    read(times);
    while(times--) {
        solve();   
    }
    return 0;
}