题目描述

剑舞正在与游戏中的最终 Boss 展开一场惊心动魄的决斗。Boss 敌人的生命值为 h。剑舞拥有 n 次攻击手段。第 i 次攻击能对 Boss 造成 ai 点伤害，但其冷却时间为 ci 回合，这意味着若当前回合是 x，那么下一次可以使用此攻击的时间是回合 x+ci。每个回合，剑舞都能够一次性使出所有当前未处于冷却状态的攻击。倘若所有攻击均处于冷却状态，剑舞便会在该回合不采取任何行动，直接进入下一回合。 起初，所有攻击均未处于冷却状态。那么剑舞需要多少回合才能成功击败 Boss 呢？当 Boss 的生命值降为 0 或更低时，即视为被击败。

输入格式

第一行包含 t (1≤t≤1e4) 。 每个测试用例的第一行包含两个整数 h 和 n (1≤h,n≤21e5)。 每个测试用例的下一行包含 n 个整数 a1,a2,...,an (1≤ai≤21e5) 。 每个测试用例的下一行包含 n 个整数 c1,c2,...,cn (1≤ci≤21e5) 。 保证所有测试用例的 h 与 n 之和不超过 21e5。

输出格式

对于每个测试用例，输出一个整数，即剑舞击败 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 位整数，因为答案可能会很大。