#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define rep(a, b, c) for(int (a)=(b);(a)<=(c);(a)++)
#define per(a, b, c) for(int (a)=(b);(a)>=(c);(a)--)
#define mset(var, val) memset(var,val,sizeof(var))
#define ll long long
#define int ll
#define fi first
#define se second
#define no "NO\n"
#define yes "YES\n"
#define pb push_back
#define endl "\n"
#define pii pair<int,int>
#define pll pair<ll,ll>

#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)

void err() { cout << '\n'; }

template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout << arg << ' ';
    err(args...);
}

const int N = 1e6 + 5;
const int inf = 1e18;

int a[N],cost[N<<1],dp[N<<1];
int n,m,k;

void upd(){
    rep(i,1,m*2){
        dp[i]=inf;
    }
    dp[1]=0;
    for(int i=2;i<=m*2;i++){
        if(dp[i]==inf){
            dp[i]=cost[i];
        }
        for(int j=i;j<=m*2;j+=i){
            dp[j]=min(min(dp[j],dp[i]+cost[j/i]),cost[j]);
        }
    }
}

bool check(int x){
    int sum=0;
    if(x==0){
        rep(i,1,(n+1)/2){
            sum+=dp[a[i]+1];
        }
    }else{
        rep(i,1,(n+1)/2){
            sum+=dp[a[i]/x];
        }
    }
    if(sum<=k){
        return true;
    }
    return false;
}

void solve() {
    cin>>n>>m>>k;
    rep(i,1,n){
        cin>>a[i];
    }
    rep(i,1,m){
        cin>>cost[i];
    }
    upd();
    sort(a+1,a+1+n);
    per(i,m,1){
        dp[i]=min(dp[i],dp[i+1]);
    }
    int l=0,r=a[(n+1)/2],ans=r;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    cout<<ans<<endl;
}

signed main() {
    IOS;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}
/*
 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

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

1
 5 10 5
3 7 1 10 10
11 6 11 6 1 8 9 1 3 1
 * */