← 返回题目列表

Codeforces · 1985/F

F. 最终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 的生命值和你的攻击次数。

每个测试用例的以下行包含 $$$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 位整数,因为答案可能会变大。