A6548. 「NOI2018」屠龙勇士

小 D 最近在网上发现了一款小游戏。游戏的规则如下：
* 游戏的目标是按照编号 $1$~$n$ 顺序杀掉 $n$ 条巨龙，每条巨龙拥有一个初始的生命值 $a_i$ 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 $p_i$，直至生命值非负。只有在**攻击结束后**且当生命值**恰好**为 $0$ 时它才会死去。
* 游戏开始时玩家拥有 $m$ 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。

小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格， 于是小 D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：
* 每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中**攻击力最大**的一把剑作为武器。如果没有这样的剑，则选择**攻击力最低**的一把剑作为武器。
* 机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙**固定的** $x$ 次，使巨龙的生命值减少 $x \times ATK$。
* 之后，巨龙会不断使用恢复能力，每次恢复 $p_i$ 生命值。若在使用恢复能力前或某一次恢复后其生命值为 $0$，则巨龙死亡，玩家通过本关。

那么显然机器人的**攻击次数**是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数 $x$ 设置为多少，才能用最少的攻击次数通关游戏吗？

当然如果无论设置成多少都无法通关游戏，输出 $-1$ 即可。

从文件 dragon.in 中读入数据。

第一行一个整数 $T$，代表数据组数。

接下来 $T$ 组数据，每组数据包含 $5$ 行。
* 每组数据的第一行包含两个整数，$n$ 和 $m$，代表巨龙的数量和初始剑的数量；
* 接下来一行包含 $n$ 个正整数，第 $i$ 个数表示第 $i$ 条巨龙的初始生命值 $a_i$；
* 接下来一行包含 $n$ 个正整数，第 $i$ 个数表示第 $i$ 条巨龙的恢复能力 $p_i$；
* 接下来一行包含 $n$ 个正整数，第 $i$ 个数表示杀死第 $i$ 条巨龙后奖励的剑的攻击力；
* 接下来一行包含 $m$ 个正整数，表示初始拥有的 $m$ 把剑的攻击力。

输出到文件 dragon.out 中。

一共 $T$ 行。

第 $i$ 行一个整数，表示对于第 $i$ 组数据，能够使得机器人通关游戏的最小攻击次数 $x$，如果答案不存在，输出 $-1$。

| 测试点编号 | $n$ | $m$ | $p_i$ | $a_i$ | 攻击力 | 其他限制 |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| 1 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | 无 |
| 2 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | 无 |
| 3 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $\le 10^5$ | 无 |
| 4 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $\le 10^5$ | 无 |
| 5 | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | 特性 1、特性 2 |
| 6 | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | 特性 1、特性 2 |
| 7 | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | 特性 1、特性 2 |
| 8 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | 特性 1 |
| 9 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | 特性 1 |
| 10 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | 特性 1 |
| 11 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | 特性 1 |
| 12 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | 特性 1 |
| 13 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | 特性 1 |
| 14 | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | 无特殊限制 |
| 15 | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | 无特殊限制 |
| 16 | $\le 10^5$ | $\le 10^5$ | 所有 $p_i$ 是质数 | $\le 10^{12}$ | $\le 10^6$ | 特性 1 |
| 17 | $\le 10^5$ | $\le 10^5$ | 所有 $p_i$ 是质数 | $\le 10^{12}$ | $\le 10^6$ | 特性 1 |
| 18 | $\le 10^5$ | $\le 10^5$ | 无特殊限制 | $\le 10^{12}$ | $\le 10^6$ | 特性 1 |
| 19 | $\le 10^5$ | $\le 10^5$ | 无特殊限制 | $\le 10^{12}$ | $\le 10^6$ | 特性 1 |
| 20 | $\le 10^5$ | $\le 10^5$ | 无特殊限制 | $\le 10^{12}$ | $\le 10^6$ | 特性 1 |

特性 1 是指：对于任意的 $i$，$a_i \le p_i$。

特性 2 是指：$\operatorname{lcm}(p_i) \le 10^6$，即所有 $p_i$ 的最小公倍数不大于 $10^6$。

对于所有的测试点，$T \le 5$，所有武器的攻击力 $\le 10^6$，所有 $p_i$ 的***最小公倍数*** $\le 10^{12}$。

#### 提示
你所用到的中间结果可能很大，注意保存中间结果的变量类型。