#include <bits/stdc++.h>

using namespace std;

const int INF = (int) 1e9 + 10;

const int N = 1'000'100;
vector< int > divs[N];

int solve()
{
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k );

	vector< int > a ( n );
	for( auto &x : a )
		scanf("%d", &x );

	sort( a.begin(), a.end() );

	vector< int > cost( m + 1 );
	for( int i = 1; i <= m; ++ i )
		scanf("%d", &cost[i] );

	int low = -1, high = m;
	while( high - low > 1 )
	{
		const int mid = ( low + high ) / 2;

		vector< int > C( m + 1 );
		for( int x = 0; x <= m; ++ x )
			C[x] = ( x > mid ? INF : 0 );

		int best_gt = INF;
		for( int i = m; i >= 1; -- i )
		{
			if( best_gt < C[i] )
				C[i] = best_gt;
			best_gt = min( best_gt, cost[i] );
		}

		for( int x = 1; x <= m; ++ x )
		{
			for( auto &d : divs[x] )
			{
				const int nx = min( m, x + d - 1 );
				C[x] = min( C[x], C[nx] );
			}

			for( int i = 2; i * x <= m; ++ i )
			{
				const int n_cost = min( INF, C[x] + cost[i] );
				const int last = min( m, i * ( x + 1 ) - 1 );

				if( n_cost < C[last] )
					C[last] = n_cost;
			}
		}

		long long real_cost = 0;
		for( int i = 0; i <= ( n / 2 ); ++ i )
			real_cost += C[a[i]];

		if( real_cost <= k ) high = mid;
		else low = mid;
	}
	return high;
}

int main() {

	for( int d = 2; d < N; ++ d )
		for( int x = d; x < N; x += d )
			divs[x].push_back( d );

	int t;
	scanf("%d", &t );
	while( t-- )
	{
		printf("%d\n", solve() );
	}
	return 0;
}