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

int main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(0) ;

    const int up = 1e6 ;
    vector<vector<int>> factor(up + 1) ;
    for(int i = 2 ; i <= up ; i ++)
        for(int j = i + i ; j <= up ; j += i)
            factor[j].push_back(i) ;

    int T ;
    cin >> T ;
    while(T --)
    {
        int n , m , k ;
        cin >> n >> m >> k ;
        vector<int> a(n + 1 , 0) ;
        for(int i = 1 ; i <= n ; i ++)  cin >> a[i] ;
        vector<int> cost(m + 2 , 0) ;
        for(int i = 1 ; i <= m ; i ++)  cin >> cost[i] ;
        cost[m + 1] = k + 1 ;
        for(int i = m - 1 ; i >= 1 ; i --)  cost[i] = min(cost[i] , cost[i + 1]) ;
        for(int i = 2 ; i <= m ; i ++)
            for(auto u : factor[i])
            {
                int v = i / u ;
                cost[i] = min(cost[i] , cost[u] + cost[v]) ;
            }
        for(int i = m - 1 ; i >= 1 ; i --)  cost[i] = min(cost[i] , cost[i + 1]) ;
        int l = 0 , r = m ;
        int res = r ;
        auto ok = [&](int x)
        {
            int p = n / 2 ;
            vector<int> v ;
            for(int i = 1 ; i <= n ; i ++)
                if(a[i] > x)
                    v.push_back(a[i]) ;
            if(v.size() <= p)  return true ;
            sort(v.begin() , v.end()) ;
            int cur = v.size() ;
            int t = k ;
            for(auto u : v)
            {
                int z = (u + 1 + x) / (x + 1) ; // u / z <= x
                assert(z <= m + 1) ;
                if(cost[z] <= t)  t -= cost[z] , cur -= 1 ;
                else  break ;
            }
            return cur <= p ;
        } ;
        while(l <= r)
        {
            int mid = (l + r) / 2 ;
            if(ok(mid))  res = mid , r = mid - 1 ;
            else  l = mid + 1 ;
        }
        cout << res << '\n' ;
    }

    return 0 ;
}
/*



*/