You are facing the final boss in your favorite video game. The boss enemy has h
 health. Your character has n
 attacks. The i
'th attack deals ai
 damage to the boss but has a cooldown of ci
 turns, meaning the next time you can use this attack is turn x+ci
 if your current turn is x
. Each turn, you can use all attacks that are not currently on cooldown, all at once. If all attacks are on cooldown, you do nothing for the turn and skip to the next turn.

Initially, all attacks are not on cooldown. How many turns will you take to beat the boss? The boss is beaten when its health is 0
 or less.

Input
The first line contains t
 (1≤t≤104
)  – the number of test cases.

The first line of each test case contains two integers h
 and n
 (1≤h,n≤2⋅105
) – the health of the boss and the number of attacks you have.

The following line of each test case contains n
 integers a1,a2,...,an
 (1≤ai≤2⋅105
) – the damage of your attacks.

The following line of each test case contains n
 integers c1,c2,...,cn
 (1≤ci≤2⋅105
) – the cooldown of your attacks.

It is guaranteed that the sum of h
 and n
 over all test cases does not exceed 2⋅105
.

Output
For each test case, output an integer, the minimum number of turns required to beat the boss.

Example
InputCopy
8
3 2
2 1
2 1
5 2
2 1
2 1
50 3
5 6 7
5 6 7
50 3
2 2 2
3 3 3
90000 2
200000 200000
1 1
100000 1
1
200000
6 7
3 2 3 2 3 1 2
6 5 9 5 10 7 7
21 6
1 1 1 1 1 1
5 5 8 10 7 6
OutputCopy
1
3
15
25
1
19999800001
1
21
Note
For the first test case, you can use attacks 1
 and 2
 on the first turn, dealing 3
 damage in total, and slaying the boss.

For the second case, you can beat the boss in 3
 turns by using the following attacks:

Turn 1
: Use attacks 1
 and 2
, dealing 3
 damage to the boss. The boss now has 2
 health left.

Turn 2
: Use attack 2
, dealing 1
 damage to the boss. The boss now has 1
 health left.

Turn 3
: Use attack 1
, dealing 2
 damage to the boss. The boss now has −1
 health left. Since its health is less than or equal to 0
, you beat the boss.

For the sixth test case: remember to use 64-bit integers as the answer can get large.#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define endl '\n'
#define pb push_back
#define speedyboy ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin() , x.end()
#define F first
#define S second
#define pll pair<ll , ll>
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;

ll i , j , k , ans;
const ll sz = 5e5 + 5 , INF = 1e18 , MOD = 1e9 + 7;
ll a[sz] , b[sz];

void solve(){
    ll n , m , x = 0;
    cin >> n >> m;
    for(i = 1 ; i <= m ; i++){
        cin >> a[i];
    }
    for(i = 1 ; i <= m ; i++){
        cin >> b[i];
    }
    ll l = 1 , r = 1e18 , mid , best;
    while(l <= r){
        ll sum = 0;
        mid = (l + r) >> 1;
        for(i = 1 ; i <= m ; i++){
            sum += (mid / b[i]) * a[i];
        }
        if(sum > n){
            best = mid;
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    cout << best << endl;
}


signed main(){
    speedyboy;
    ll t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}
Kodumda bazı aksaklıklar var düzeltsene