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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  const int MX = 3e6+7;
  vector<vector<int>>  divisors(MX);
  for (int64_t i = 1; i < MX; i++) {
    for (int64_t j = i*i; j < MX; j+=i){
      divisors[j].push_back(i);
    }
  }

  int tt;
  cin >> tt;
  while(tt--) {
    int n, m, k;
    cin >> n >> m >> k;
    m *= 3;
    vector<int64_t> cost(m+1), a(n);
    for (auto& x :a) cin >> x;
    for (int i = 1; i <= m; i++) {
      if (3*i <= m)
        cin >> cost[i];
      else
        cost[i] = 1e16;
    }
    for (int _ = 0; _ < 15; _++) {
      for (int i = 1; i <= m; i++) {
        for (auto& d : divisors[i]) {
          cost[i] = min(cost[i], cost[d] + cost[i/d]);
        }
      }
      for (int i = m-1; i >= 1; i--) {
        cost[i] = min(cost[i], cost[i+1]);
      }
    }

    auto check = [&](int64_t M) -> int64_t {
      vector<int64_t> costs;
      for (int i =0; i < n; i++) {
        if (a[i] <= M) costs.push_back(0);
        else {
          int64_t denom = max(int64_t(1), (a[i]+M)/(M+1));
          while (a[i]/denom <= M) denom--;
          while(a[i]/denom > M) denom++;
          costs.push_back(cost[denom]);
        }
      }
      sort(costs.begin(), costs.end());
      int64_t tot = 0;
      for (int i = 0; i < (n+1)/2; i++) tot += costs[i];
      return tot;
    };

    int L = 0, R = 5e6;
    while(L < R) {
      int M = (L+R)/2;
      auto tot = check(M);
      if (tot > k) {
        L = M+1;
      } else {
        R = M;
      }
    }
    cout << L << '\n';
  }
}