#2721. 「NOI2018」屠龙勇士

内存限制:512 MiB 时间限制:2000 ms 输入文件: dragon.in 输出文件: dragon.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 D 最近在网上发现了一款小游戏。游戏的规则如下:

  • 游戏的目标是按照编号 111~nnn 顺序杀掉 nnn 条巨龙,每条巨龙拥有一个初始的生命值 aia_iai 。同时每条巨龙拥有恢复能力,当其使用恢复能力时,它的生命值就会每次增加 pip_ipi,直至生命值非负。只有在攻击结束后且当生命值恰好000 时它才会死去。
  • 游戏开始时玩家拥有 mmm 把攻击力已知的剑,每次面对巨龙时,玩家只能选择一把剑,当杀死巨龙后这把剑就会消失,但作为奖励,玩家会获得全新的一把剑。

小 D 觉得这款游戏十分无聊,但最快通关的玩家可以获得 ION2018 的参赛资格, 于是小 D 决定写一个笨笨的机器人帮她通关这款游戏,她写的机器人遵循以下规则:

  • 每次面对巨龙时,机器人会选择当前拥有的,攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑,则选择攻击力最低的一把剑作为武器。
  • 机器人面对每条巨龙,它都会使用上一步中选择的剑攻击巨龙固定的 xxx 次,使巨龙的生命值减少 x×ATKx \times ATKx×ATK
  • 之后,巨龙会不断使用恢复能力,每次恢复 pip_ipi 生命值。若在使用恢复能力前或某一次恢复后其生命值为 000,则巨龙死亡,玩家通过本关。

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

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

输入格式

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

第一行一个整数 TTT,代表数据组数。

接下来 TTT 组数据,每组数据包含 555 行。

  • 每组数据的第一行包含两个整数,nnnmmm,代表巨龙的数量和初始剑的数量;
  • 接下来一行包含 nnn 个正整数,第 iii 个数表示第 iii 条巨龙的初始生命值 aia_iai
  • 接下来一行包含 nnn 个正整数,第 iii 个数表示第 iii 条巨龙的恢复能力 pip_ipi
  • 接下来一行包含 nnn 个正整数,第 iii 个数表示杀死第 iii 条巨龙后奖励的剑的攻击力;
  • 接下来一行包含 mmm 个正整数,表示初始拥有的 mmm 把剑的攻击力。

输出格式

输出到文件 dragon.out 中。

一共 TTT 行。

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

样例

样例 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

样例 1 解释

第一组数据:

  • 开始时拥有的剑的攻击力为 {1,9,10}\{1,9,10\}{1,9,10},第 111 条龙生命值为 333,故选择攻击力为 111 的剑,攻击 595959 次,造成 595959 点伤害,此时龙的生命值为 −56-5656,恢复 141414 次后生命值恰好为 000,死亡。
  • 攻击力为 111 的剑消失,拾取一把攻击力为 777 的剑,此时拥有的剑的攻击力为 {7,9,10}\{7,9,10\}{7,9,10},第 222 条龙生命值为 555,故选择攻击力为 777 的剑,攻击 595959 次,造成 413413413 点伤害,此时龙的生命值为 −408-408408,恢复 686868 次后生命值恰好为 000,死亡。
  • 此时拥有的剑的攻击力为 {3,9,10}\{3,9,10\}{3,9,10},第 333 条龙生命值为 777,故选择攻击力为 333 的剑,攻击 595959 次,造成 177177177 点伤害,此时龙的生命值为 −170-170170,恢复 171717 次后生命值恰好为 000,死亡。
  • 没有比 595959 次更少的通关方法,故答案为 595959

第二组数据:

  • 不存在既能杀死第一条龙又能杀死第二条龙的方法,故无法通关,输出 −1-11

样例 2

见附加文件中的 dragon2.indragon2.ans

数据范围与提示

测试点编号 nnn mmm pip_ipi aia_iai 攻击力 其他限制
1 ≤105\le 10^5105 =1=1=1 =1=1=1 ≤105\le 10^5105 =1=1=1
2 ≤105\le 10^5105 =1=1=1 =1=1=1 ≤105\le 10^5105 =1=1=1
3 ≤105\le 10^5105 =1=1=1 =1=1=1 ≤105\le 10^5105 ≤105\le 10^5105
4 ≤105\le 10^5105 =1=1=1 =1=1=1 ≤105\le 10^5105 ≤105\le 10^5105
5 ≤103\le 10^3103 ≤103\le 10^3103 ≤105\le 10^5105 ≤105\le 10^5105 ≤105\le 10^5105 特性 1、特性 2
6 ≤103\le 10^3103 ≤103\le 10^3103 ≤105\le 10^5105 ≤105\le 10^5105 ≤105\le 10^5105 特性 1、特性 2
7 ≤103\le 10^3103 ≤103\le 10^3103 ≤105\le 10^5105 ≤105\le 10^5105 ≤105\le 10^5105 特性 1、特性 2
8 =1=1=1 =1=1=1 ≤108\le 10^8108 ≤108\le 10^8108 ≤106\le 10^6106 特性 1
9 =1=1=1 =1=1=1 ≤108\le 10^8108 ≤108\le 10^8108 ≤106\le 10^6106 特性 1
10 =1=1=1 =1=1=1 ≤108\le 10^8108 ≤108\le 10^8108 ≤106\le 10^6106 特性 1
11 =1=1=1 =1=1=1 ≤108\le 10^8108 ≤108\le 10^8108 ≤106\le 10^6106 特性 1
12 =1=1=1 =1=1=1 ≤108\le 10^8108 ≤108\le 10^8108 ≤106\le 10^6106 特性 1
13 =1=1=1 =1=1=1 ≤108\le 10^8108 ≤108\le 10^8108 ≤106\le 10^6106 特性 1
14 =105=10^5=105 =105=10^5=105 =1=1=1 ≤108\le 10^8108 ≤106\le 10^6106 无特殊限制
15 =105=10^5=105 =105=10^5=105 =1=1=1 ≤108\le 10^8108 ≤106\le 10^6106 无特殊限制
16 ≤105\le 10^5105 ≤105\le 10^5105 所有 pip_ipi 是质数 ≤1012\le 10^{12}1012 ≤106\le 10^6106 特性 1
17 ≤105\le 10^5105 ≤105\le 10^5105 所有 pip_ipi 是质数 ≤1012\le 10^{12}1012 ≤106\le 10^6106 特性 1
18 ≤105\le 10^5105 ≤105\le 10^5105 无特殊限制 ≤1012\le 10^{12}1012 ≤106\le 10^6106 特性 1
19 ≤105\le 10^5105 ≤105\le 10^5105 无特殊限制 ≤1012\le 10^{12}1012 ≤106\le 10^6106 特性 1
20 ≤105\le 10^5105 ≤105\le 10^5105 无特殊限制 ≤1012\le 10^{12}1012 ≤106\le 10^6106 特性 1

特性 1 是指:对于任意的 iiiai≤pia_i \le p_iaipi

特性 2 是指:lcm⁡(pi)≤106\operatorname{lcm}(p_i) \le 10^6lcm(pi)106,即所有 pip_ipi 的最小公倍数不大于 10610^6106

对于所有的测试点,T≤5T \le 5T5,所有武器的攻击力 ≤106\le 10^6106,所有 pip_ipi最小公倍数 ≤1012\le 10^{12}1012

提示

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