#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

using LL=long long;
//#define int LL
const int N=1e6+10;
const int M=N*2;
int n,m;
int k;
using PII=pair<int,int>;

vector<PII>p[1000005];
void init() {
    for(int i=2;i<=1000000;i++)
    {
        for(int j=i;j<=1000000;j+=i)
        {
            p[j].push_back({i,j/i});
        }
    }
}
inline LL min(LL a,LL b) {
    return a>b?b:a;
}
int a[N];
LL cost[N];
LL Real[N];
LL suf[N];
void solve() {
    //vector<int>a(n+1);
    /*vector<LL>cost(m+1);
    vector<LL>Real(m+1,1e18);
    vector<LL>suf(m+1);*/
    cin>>n>>m>>k;

    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>cost[i];
    for(int i=2;i<=m;i++)Real[i]=cost[i];
    Real[1]=1e18;
    Real[m+1]=1e18;
    //cerr<<"???"<<"\n";
    for(int i=2;i<=m;i++) {
        for(auto [t1,t2]:p[i]) {
            //cerr<<"t1="<<t1<<" t2="<<t2<<"\n";
            Real[i]=min(Real[i],Real[t1]+Real[t2]);
        }
    }

    for(int i=m;i>=1;i--) {
        if(i==m)suf[i]=Real[i];
        else {
            suf[i]=min(suf[i+1],Real[i]);
        }
    }

    for(int i=2;i<=m;i++) {
        Real[m+1]=min(Real[m+1],Real[i]+suf[(m+i)/i]);
    }

    for(int i=m+1;i>=1;i--) {
        if(i==m+1)suf[i]=Real[i];
        else {
            suf[i]=min(suf[i+1],Real[i]);
        }
    }
    suf[1]=0;

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


    auto check=[&](int x) {
        /*int cnt=0,p=0;
        for(int i=1;i<=n;i++) {
            if(a[i]<=x)cnt++;
            else {
                p=i;
                break;
            }
        }
        if(cnt>=n/2+1)return true;
        int num=n/2+1-cnt;
        LL tot=0;
        for(int i=p;i<=p+num-1;i++) {
            int need;
            if(x)need=(a[i]+x-1)/x;
            else need=a[i]+1;
            need=min(need,m+1);
            tot+=suf[need];
            if(tot>k)return false;
        }
        return true;*/

        LL tot=0;
        for(int i=1;i<=n/2+1;i++) {
            if(a[i]<=x)continue;
            int need;
            if(x==0)need=a[i]+1;
            else {
                need=a[i]/x;
                if(a[i]%x)need++;
            }
            tot+=suf[need];
        }
        return tot<=k;

        LL sum=0;
        for(int i=1;i<=n/2+1;i++) {
            sum+=suf[a[i]/(x+1)+1];
        }
        return sum<=k;
    };
    if(check(0)) {
        cout<<"0\n";
        return;
    }
    int l=0,r=a[n/2+1];
    int res=0;
    while(l<=r) {
        int mid=(l+r)/2;

        if(check(mid))res=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<res<<"\n";
}
/*
1
3 5 0
2 5 2
3 2 4 6 13

1
3 5 3
2 5 3
3 2 4 6 13

1
3 5 6
2 5 2
3 2 4 6 13

3
3 5 0
2 5 2
3 2 4 6 13
3 5 3
2 5 3
3 2 4 6 13
3 5 6
2 5 2
3 2 4 6 13

 */
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    cin>>T;
    init();
    //find_prime(1000005);
    while(T--)solve();
    return 0;
}