F. Final Boss
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 $$$a_i$$$ damage to the boss but has a cooldown of $$$c_i$$$ turns, meaning the next time you can use this attack is turn $$$x + c_i$$$ 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 \leq t \leq 10^4$$$)  – the number of test cases.

The first line of each test case contains two integers $$$h$$$ and $$$n$$$ ($$$1 \leq h, n \leq 2 \cdot 10^5$$$) – the health of the boss and the number of attacks you have.

The following line of each test case contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq 2 \cdot 10^5$$$) – the damage of your attacks.

The following line of each test case contains $$$n$$$ integers $$$c_1, c_2, ..., c_n$$$ ($$$1 \leq c_i \leq 2 \cdot 10^5$$$) – the cooldown of your attacks.

It is guaranteed that the sum of $$$h$$$ and $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

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

Example
Input
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
Output
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.