//  Nikita Golikov, 2023

#include <bits/stdc++.h>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#ifdef GOLIKOV
  #include "/Users/golikovnik/contests/debug.h"
#else
  #define debug(...) ;
#endif

template <class A, class B>
bool smin(A& x, B&& y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}

template <class A, class B>
bool smax(A& x, B&& y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}

void solveTest() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> a(n);
  for (auto& x : a) {
    cin >> x;
  }
  vector<ll> cost(m + 2);
  for (int i = 1; i <= m; ++i) {
    cin >> cost[i];
  }
  cost[1] = 0;
  vector<vector<int>> divisors(m + 1);
  for (int i = 1; i <= m; ++i) {
    for (int j = 2 * i; j <= m; j += i) {
      divisors[j].push_back(i);
    }
  }
  for (int i = 1; i <= m; ++i) {
    for (int j : divisors[i]) {
      smin(cost[i], cost[j] + cost[i / j]);
    }
  }
  for (int i = m - 1; i >= 1; --i) {
    smin(cost[i], cost[i + 1]);
  }
  cost[m + 1] = 1e18;
  for (int i = m; i >= 2; --i) {
    smin(cost[m + 1], cost[i] + cost[(m + i) / i]);
  }
  for (int i = m; i >= 1; --i) {
    smin(cost[i], cost[i + 1]);
  }
  debug(cost);

  vector<ll> dp(n);
  auto check = [&](int bound) {
    for (int i = 0; i < n; ++i) {
      int r = max(1, a[i] / (bound + 1) - 3);
      while (a[i] / r > bound) {
        ++r;
      }
      assert(r <= m + 1);
      dp[i] = cost[r];
    }
    debug(bound, dp);
    sort(dp.begin(), dp.end());
    int cnt = 0;
    ll sum = 0;
    while (cnt < n && sum + dp[cnt] <= k) {
      sum += dp[cnt++];
    }
    return cnt >= (n + 1) / 2;
  };

  int left = -1;
  int right = m;
  while (left + 1 != right) {
    int mid = (left + right) / 2;
    (check(mid) ? right : left) = mid;
  }
  cout << right << '\n';
}

int main() {
#ifdef GOLIKOV
  assert(freopen("in", "rt", stdin));
  auto _clock_start = chrono::high_resolution_clock::now();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int tests_;
  cin >> tests_;
  for (int tt_ = 1; tt_ <= tests_; ++tt_) {
    solveTest();
  }

#ifdef GOLIKOV
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
      chrono::high_resolution_clock::now()
          - _clock_start).count() << "ms." << endl;
#endif
  return 0;
}