以下题面由 AI 翻译。

题目描述

你正在面对你最喜欢的视频游戏中的最终Boss。Boss敌人有$h$点生命值。你的角色有$n$种攻击方式。第$i$次攻击对Boss造成$a_i$点伤害，但需要冷却$c_i$回合，这意味着如果当前回合是第$x$回合，下次可以使用这个攻击的回合是第$x + c_i$回合。每个回合，你可以同时使用所有当前没有冷却的攻击。如果所有攻击都在冷却中，你这个回合什么都不做，直接跳到下一个回合。

初始时，所有攻击都不在冷却中。你需要多少回合才能打败Boss？当Boss的生命值不超过$0$时，Boss就被打败了。

输入格式

第一行包含$t(1 \leq t \leq 10^4)$ 个测试用例数。

每个测试用例的第一行包含两个整数$h$和$n$ ($1 \leq h, n \leq 2 \cdot 10^5$)，分别表示Boss的生命值和你拥有的攻击方式数。

每个测试用例的下一行包含$n$个整数$a_1, a_2, ..., a_n$ ($1 \leq a_i \leq 2 \cdot 10^5$)，表示你的攻击伤害。

每个测试用例的下一行包含$n$个整数$c_1, c_2, ..., c_n$ ($1 \leq c_i \leq 2 \cdot 10^5$)，表示你的攻击冷却时间。

保证所有测试用例中$h$和$n$的总和不超过$2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示打败Boss所需的最少回合数。

样例数据

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

1
3
15
25
1
19999800001
1
21

数据范围与提示

对于第一个测试用例，你可以在第一个回合使用攻击1和2，总共造成3点伤害，从而击败Boss。

对于第二个测试用例，你可以在3回合内打败Boss，使用以下攻击方式：

第1回合：使用攻击1和2，对Boss造成3点伤害。Boss剩余2点生命值。

第2回合：使用攻击2，对Boss造成1点伤害。Boss剩余1点生命值。

第3回合：使用攻击1，对Boss造成2点伤害。Boss剩余-1点生命值。由于其生命值小于或等于0，你击败了Boss。

对于第六个测试用例：记得使用64位整数，因为答案可能会很大。