#include<bits/stdc++.h>
#define ll long long
#define SD ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define flot(n) cout << setprecision(n) << setiosflags(ios::fixed) << setiosflags(ios::showpoint)
#define all(a) (a).begin() , (a).end()
#define F first
#define S second
#define pii pair<int,int>
#define pb push_back
#define piii pair<pii,int>
#define endl '\n'
//#define int ll
using namespace std;
void readFromFile(string input = "input.txt",string output="output.txt") {
    #ifndef ONLINE_JUDGE
        freopen(input.c_str(),"r",stdin);
        freopen(output.c_str(),"w",stdout);
    #endif
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll x, ll y) {
    return uniform_int_distribution<ll>(x, y)(rng);
}
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const long double EPS = 1e-6;
const long double pi = acos(-1.0);
const int mod=1e9+7;
const int N = 1e6+5;
const int sq = 500;
int n,m,k,a[N],c[N],dp[N];
bool can(int mid) {
    ll cost=0;
    for(int i = 0 ; i <= n/2 ; i++) {
        if(a[i] <= mid) continue;
        if(mid==0) {
            cost += dp[a[i]+1];
        }else {
            int l = 1 , r = m , mid2 , ans;
            while(l <= r) {
                mid2 = (l+r)/2;
                if(a[i]/mid2 <= mid) {
                    ans = mid2;
                    r = mid2-1;
                }else l = mid2+1;
            }
            cost += dp[ans];
        }
        if(cost > k) return 0;
    }
    return 1;
}
void solve(int T) {

    for(int i = 0 ; i < n ; i++) {
        cin >> a[i];
    }
    if(T == 34) {
        string s;
        char z = '@';
        s += to_string(n);s += z;
        s += to_string(m);s += z;
        s += to_string(k);s += z;s += z;
        for(int i = 0 ; i < n ; i++){
        s += to_string(a[i]);s += z;
        }
        for(int i = 1 ; i <= m ; i++){
        s += to_string(c[i]);s += z;
        }
        cout << s << endl;
    }
    sort(a,a+n);
    for(int i = 1 ; i <= m ; i++) {
        cin >> c[i];
        dp[i] = c[i];
    }
    c[m+1] = dp[m+1] = 1e9+1;m++;
    for(int i = m-1 ; i >= 1 ; i--) {
        dp[i] = min(dp[i],dp[i+1]);
    }
    for(int i = 1 ; i <= m ; i++) {
        for(int j = i ; j <= m ; j += i) {
            dp[j] = min(dp[j],c[i]+dp[j/i]);
        }
    }
    for(int i = m-1 ; i >= 1 ; i--) {
        dp[i] = min(dp[i],dp[i+1]);
    }
    int l = 0 , r = m , mid , ans;
    while(l <= r) {
        mid = (l+r)/2;
        if(can(mid)) {
            ans = mid;
            r = mid-1;
        }else l = mid+1;
    }
    cout << ans << endl;
}
int main() {
//    readFromFile();
    SD;
    int t = 1;
    cin >> t;
    for(int i = 0 ; i < t ; i++){
        solve(i+1);
    }
}