您正在面对您最喜欢的电子游戏中的最终老板。 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 的生命值和你的攻击次数。
每个测试用例的以下行包含 $$$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 所需的最小回合数。
示例
输入 #1
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
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$$$,所以你击败了老板。
对于第六个测试用例:记住使用 64 位整数,因为答案可能会变大。