A92980.「NOI2018」屠龙勇士
省选/NOI-
NOI
通过率：0%
时间限制：2.00s
内存限制：512MB
题目描述
小 D 最近在网上发现了一款小游戏。游戏的规则如下：
- 游戏的目标是按照编号 1~n 顺序杀掉 n 条巨龙，每条巨龙拥有一个初始的生命值 ai 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 pi，直至生命值非负。只有在攻击结束后且当生命值恰好为 0 时它才会死去。
- 游戏开始时玩家拥有 m 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。
小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格， 于是小 D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：
- 每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择攻击力最低的一把剑作为武器。
- 机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 x 次，使巨龙的生命值减少 x×ATK。
- 之后，巨龙会不断使用恢复能力，每次恢复 pi 生命值。若在使用恢复能力前或某一次恢复后其生命值为 0，则巨龙死亡，玩家通过本关。
那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数 x 设置为多少，才能用最少的攻击次数通关游戏吗？
当然如果无论设置成多少都无法通关游戏，输出 −1 即可。
输入格式
从文件 dragon.in 中读入数据。
第一行一个整数 T，代表数据组数。
接下来 T 组数据，每组数据包含 5 行。
- 每组数据的第一行包含两个整数，n 和 m，代表巨龙的数量和初始剑的数量；
- 接下来一行包含 n 个正整数，第 i 个数表示第 i 条巨龙的初始生命值 ai；
- 接下来一行包含 n 个正整数，第 i 个数表示第 i 条巨龙的恢复能力 pi；
- 接下来一行包含 n 个正整数，第 i 个数表示杀死第 i 条巨龙后奖励的剑的攻击力；
- 接下来一行包含 m 个正整数，表示初始拥有的 m 把剑的攻击力。
输出格式
输出到文件 dragon.out 中。
一共 T 行。
第 i 行一个整数，表示对于第 i 组数据，能够使得机器人通关游戏的最小攻击次数 x，如果答案不存在，输出 −1。
输入输出样例
输入#1
2 3 3 3 5 7 4 6 10 7 3 9 1 9 1000 3 2 3 5 6 4 8 7 1 1 1 1 1
输出#1
59 -1
说明/提示
| 测试点编号 | n | m | pi | ai | 攻击力 | 其他限制 |
|---|---|---|---|---|---|---|
| 1 | ≤105 | =1 | =1 | ≤105 | =1 | 无 |
| 2 | ≤105 | =1 | =1 | ≤105 | =1 | 无 |
| 3 | ≤105 | =1 | =1 | ≤105 | ≤105 | 无 |
| 4 | ≤105 | =1 | =1 | ≤105 | ≤105 | 无 |
| 5 | ≤103 | ≤103 | ≤105 | ≤105 | ≤105 | 特性 1、特性 2 |
| 6 | ≤103 | ≤103 | ≤105 | ≤105 | ≤105 | 特性 1、特性 2 |
| 7 | ≤103 | ≤103 | ≤105 | ≤105 | ≤105 | 特性 1、特性 2 |
| 8 | =1 | =1 | ≤108 | ≤108 | ≤106 | 特性 1 |
| 9 | =1 | =1 | ≤108 | ≤108 | ≤106 | 特性 1 |
| 10 | =1 | =1 | ≤108 | ≤108 | ≤106 | 特性 1 |
| 11 | =1 | =1 | ≤108 | ≤108 | ≤106 | 特性 1 |
| 12 | =1 | =1 | ≤108 | ≤108 | ≤106 | 特性 1 |
| 13 | =1 | =1 | ≤108 | ≤108 | ≤106 | 特性 1 |
| 14 | =105 | =105 | =1 | ≤108 | ≤106 | 无特殊限制 |
| 15 | =105 | =105 | =1 | ≤108 | ≤106 | 无特殊限制 |
| 16 | ≤105 | ≤105 | 所有 pi 是质数 | ≤1012 | ≤106 | 特性 1 |
| 17 | ≤105 | ≤105 | 所有 pi 是质数 | ≤1012 | ≤106 | 特性 1 |
| 18 | ≤105 | ≤105 | 无特殊限制 | ≤1012 | ≤106 | 特性 1 |
| 19 | ≤105 | ≤105 | 无特殊限制 | ≤1012 | ≤106 | 特性 1 |
| 20 | ≤105 | ≤105 | 无特殊限制 | ≤1012 | ≤106 | 特性 1 |
特性 1 是指：对于任意的 i，ai≤pi。
特性 2 是指：lcm(pi)≤106，即所有 pi 的最小公倍数不大于 106。
对于所有的测试点，T≤5，所有武器的攻击力 ≤106，所有 pi 的最小公倍数 ≤1012。
提示
你所用到的中间结果可能很大，注意保存中间结果的变量类型。