题目描述

你正在面对你最喜欢的游戏中的最终 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 所需的最少回合数。

样例

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

样例说明

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.

来源

Codeforces 1985F，英文题名 Final Boss。