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

#define int long long
#define pi pair<int, int>
#define all(x) x.begin(), x.end()
#define endl '\n'
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

void solve() {
  int h,n;cin>>h>>n;
  vector<int> a(n),c(n);
  for(int &x:a)cin>>x;
  for(int &x:c)cin>>x;
  auto f=[&](int k)->bool{
    __int128 sum=0;
    for(int i=0;i<n;i++)sum+=(__int128)((k-1)/c[i]+1)*(__int128)a[i];
    return sum>=(__int128)h;
  };
  int lo=1,hi=1e18;
  while(lo<hi){
    int m=lo+(hi-lo)/2;
    if(f(m))hi=m;
    else lo=m+1;
  }
  cout<<lo<<endl;
}

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int t = 1;
  cin >> t;
  while(t--) solve();
}