CF1985F Final Boss

你正在面对你最喜欢的游戏中的最终 BOSS。敌人的生命值是 $h$。你的角色有 $ n $ 攻击。第 i 次攻击会对 BOSS 造成 $ a_i $ 伤害，但冷却时间为 $ c_i $ 个回合，也就是说，如果你当前的回合为 $ x $，那么下一次可以使用该攻击的时间为 $ x + c_i $ 个回合。 每个回合，你都可以一次性使用当前未冷却的所有攻击。如果所有攻击都处于冷却状态，则本回合什么也不做，跳到下一回合。 最初，所有攻击都不在冷却时间内。要花多少回合才能打败 BOSS？当 BOSS 的生命值为 $ 0 $ 或更低时，它就被打败了。

第一行包含 $ t $ ( $ 1 \leq t \leq 10^4 $ ) - 测试用例的数量。 每个测试用例的第一行包含两个整数 $ h $ 和 $ n $ ( $ 1 \leq h, n \leq 2 \cdot 10^5 $ ) - BOSS 的血量和你的攻击次数。 每个测试用例的第 $2$ 行包含 $ n $ 整数 $ a_1, a_2, ..., a_n $ ( $ 1 \leq a_i \leq 2 \cdot 10^5 $ ) - 你的攻击伤害。 每个测试用例的第 $3$ 行包含 n 个整数 $ c_1, c_2, ..., c_n $ ( $ 1 \leq c_i \leq 2 \cdot 10^5 $ ) - 你的攻击冷却时间。 保证所有测试用例中的 $ h $ 和 $ n $ 之和不超过 $ 2 \cdot 10^5 $ .

对于每个测试用例，输出一个整数，即击败 BOSS 所需的最少回合数。

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.