#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace std;
using namespace __gnu_pbds;

#define int long long 
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long

const int INF=1e9+7;
const int N=1e6+10;
const int M=1e8+7;
const int M2=1e9+13;
const double pi=3.1415926535897932384626433832795028841971; 

int arr[N], trees[4*N];

void build(int node, int start, int end)
{
	if(start == end)
	{
        // Leaf node will have a single element
		trees[node] = arr[start];
	}
	else
	{
		int mid = (start + end) / 2;
        // Recurse on the left child
		build(2*node, start, mid);
        // Recurse on the right child
		build(2*node+1, mid+1, end);
        // Internal node will have the sum of both of its children
		trees[node] = min(trees[2*node] , trees[2*node+1]);
	}
}

int query(int node, int start, int end, int l, int r)
{
	if(r < start or end < l)
	{
        // range represented by a node is completely outside the given range
		return INF;
	}
	if(l <= start and end <= r)
	{
        // range represented by a node is completely inside the given range
		return trees[node];
	}
    // range represented by a node is partially inside and partially outside the given range
	int mid = (start + end) / 2;
	int p1 = query(2*node, start, mid, l, r);
	int p2 = query(2*node+1, mid+1, end, l, r);
	return min(p1 , p2);
}

void solve(int t)
{
	int n, m, k;
	cin >> n >> m >> k;
	vector<int>v, c(m+2), dp(m+2);
	for(int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		v.push_back(x);
	}
		for(int i=1;i<=m;i++)cin >> dp[i];
		for(int i=1;i<=m;i++)
		{
			for(int j=1;i*j<=m;j++)dp[i*j] = min(dp[i*j], dp[i]+dp[j]);
		}

		for(int i=1;i<=m;i++)arr[i] = dp[i];
		sort(v.begin(), v.end());
		build(1, 1, m);
		int help = INF;
		for(int i=2;i<=m;i++)
		{
			int tmp = (m+1)/(i+1);
			tmp++;
			tmp = query(1, 1, m, tmp, m);
			help = min(help , tmp + dp[i]);	
		}
		//cout << help << " ";
		dp[m+1] = arr[m+1] = help; 
		build(1, 1, m+1);
		int lo = 1, hi = m, ans = -1;
	//cout << query(1, 1, m+1, m+1, m+1) << "\n"; 
		while(lo<=hi)
		{
			int mid = (lo+hi)/2;
			int c = 0;
			for(int i=0;i<=(n/2);i++)
			{
				if(v[i] <= mid)continue;
				int tmp = (v[i]/(mid+1));
				tmp++;
				tmp = query(1, 1, m+1, tmp, m+1);
				c += tmp;
			}
		//cout << mid << " " << c << "\n"; 
			if(c > k) lo = mid+1;
			else
			{
				ans = mid;
				hi = mid-1;
			}
		}
		int c=0;
		for(int i=0;i<=(n/2);i++)
		{
			c += query(1, 1, m+1, v[i]+1, m+1);
		}
		if(c<=k)ans = 0;
		cout << ans << "\n";
	}	

	signed main()
	{
		int t = 1;
		cin >> t;
		for(int i=1;i<=t;i++)
		{
			solve(i);
		}
		return 0;
	}

answer.code: In function ‘void solve(long long int)’:
answer.code:112:21: error: conflicting declaration ‘long long int c’
  112 |                 int c=0;
      |                     ^
answer.code:63:23: note: previous declaration as ‘std::vector<long long int> c’
   63 |         vector<int>v, c(m+2), dp(m+2);
      |                       ^
answer.code:115:27: error: no match for ‘operator+=’ (operand types are ‘std::vector<long long int>’ and ‘long long int’)
  115 |                         c += query(1, 1, m+1, v[i]+1, m+1);
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:117:21: error: no match for ‘operator<=’ (operand types are ‘std::vector<long long int>’ and ‘long long int’)
  117 |                 if(c<=k)ans = 0;
      |                    ~^~~
      |                    |  |
      |                    |  long long int
      |                    std::vector<long long int>
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1088:5: note: candidate: ‘template<class _BiIter> bool std::__cxx11::operator<=(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)’
 1088 |     operator<=(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1088:5: note:   template argument deduction/substitution failed:
answer.code:117:23: note:   ‘std::vector<long long int>’ is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
  117 |                 if(c<=k)ans = 0;
      |                       ^
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1194:5: note: candidate: ‘template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<=(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)’
 1194 |     operator<=(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1194:5: note:   template argument deduction/substitution failed:
answer.code:117:23: note:   ‘std::vector<long long int>’ is not derived from ‘std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>’
  117 |                 if(c<=k)ans = 0;
      |                       ^
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1287:5: note: candidate: ‘template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<=(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)’
 1287 |     operator<=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1287:5: note:   template argument deduction/substitution failed:
answer.code:117:23: note:   ‘std::vector<long long int>’ is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
  117 |                 if(c<=k)ans = 0;
      |                       ^
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1361:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator<=(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)’
 1361 |     operator<=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1361:5: note:   template argument deduction/substitution failed:
answer.code:117:23: note:   mismatched types ‘const std::__cxx11::sub_match<_BiIter>’ and ‘long long int’
  117 |                 if(c<=k)ans = 0;
      |                       ^
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1455:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator<=(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)’
 1455 |     operator<=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1455:5: note:   template argument deduction/substitution failed:
answer.code:117:23: note:   ‘std::vector<long long int>’ is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
  117 |                 if(c<=k)ans = 0;
      |                       ^
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answe...