小 D は最近、インターネットであるミニゲームを見つけました。ゲームのルールは次のとおりです。
- ゲームの目的は、番号 $1 \sim n$ の順に $n$ 頭のドラゴンを倒すことです。各ドラゴンの初期体力は $a_i$ です。また、各ドラゴンには回復能力があり、この能力を使うと、体力が非負になるまで 1 回につき体力が $p_i$ 増加します。ドラゴンが死ぬのは、攻撃が終了した後、体力がちょうど $0$ になったときだけです。
- ゲーム開始時、プレイヤーは攻撃力が既知の $m$ 本の剣を持っています。各ドラゴンと対峙するとき、プレイヤーは剣を 1 本だけ選べます。ドラゴンを倒すとその剣は消えますが、報酬として新しい剣を 1 本獲得します。
小 D はこのゲームをとても退屈だと思っています。しかし、最も速くクリアしたプレイヤーは ION2018 の参加資格を得られるため、小 D はゲームをクリアしてくれる単純なロボットを書くことにしました。彼女の書いたロボットは、次の規則に従います。
- ドラゴンと対峙するたびに、現在持っている剣のうち、攻撃力がドラゴンの初期体力以下であるものの中から、攻撃力が最大の剣を武器として選びます。そのような剣がない場合は、攻撃力が最小の剣を選びます。
- 各ドラゴンに対して、ロボットは前の手順で選んだ剣で一定の $x$ 回だけ攻撃し、ドラゴンの体力を $x \times ATK$ 減らします。
- その後、ドラゴンは回復能力を繰り返し使い、毎回体力を $p_i$ 回復します。回復能力を使う前、または何回か回復した後に体力が $0$ になれば、ドラゴンは死に、プレイヤーはこのステージをクリアします。
したがって、ロボットの攻撃回数が、最速でゲームをクリアできるかどうかを決める鍵となります。小 D は今、すべてのドラゴンの属性を知っており、あなたの力を試したいと思っています。最小の攻撃回数でゲームをクリアするには、ロボットの攻撃回数 $x$ をいくつに設定すればよいでしょうか？
どのように設定してもゲームをクリアできない場合は、-1 を出力してください。
入力
ファイル dragon.in からデータを読み込んでください。
1 行目には、テストケース数を表す整数 $T$ が与えられます。
続いて $T$ 個のテストケースが与えられます。各テストケースは 5 行からなります。
- 1 行目には、ドラゴンの数と最初の剣の本数を表す 2 つの整数 $n,m$ が与えられます。
- 次の行には $n$ 個の正整数が与えられます。$i$ 番目の整数は、$i$ 頭目のドラゴンの初期体力 $a_i$ を表します。
- 次の行には $n$ 個の正整数が与えられます。$i$ 番目の整数は、$i$ 頭目のドラゴンの回復能力 $p_i$ を表します。
- 次の行には $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
注記
1 番目のテストケース：
- 最初に持っている剣の攻撃力は $\{1,9,10\}$ です。1 頭目のドラゴンの体力は $3$ なので、攻撃力 $1$ の剣を選びます。$59$ 回攻撃して $59$ のダメージを与えると、体力は $-56$ になります。$14$ 回回復すると体力がちょうど $0$ になり、ドラゴンは死にます。
- 攻撃力 $1$ の剣が消え、攻撃力 $7$ の剣を拾います。現在持っている剣の攻撃力は $\{7,9,10\}$ です。2 頭目のドラゴンの体力は $5$ なので、攻撃力 $7$ の剣を選びます。$59$ 回攻撃して $413$ のダメージを与えると、体力は $-408$ になります。$68$ 回回復すると体力がちょうど $0$ になり、ドラゴンは死にます。
- この時点で持っている剣の攻撃力は $\{3,9,10\}$ です。3 頭目のドラゴンの体力は $7$ なので、攻撃力 $3$ の剣を選びます。$59$ 回攻撃して $177$ のダメージを与えると、体力は $-170$ になります。$17$ 回回復すると体力がちょうど $0$ になり、ドラゴンは死にます。
- $59$ 回より少ない攻撃回数でクリアする方法はないため、答えは $59$ です。
2 番目のテストケース：
- 1 頭目と 2 頭目のドラゴンを両方倒せる方法がないため、クリアできません。
-1を出力します。
入出力例 2
選手用ディレクトリ内の dragon/dragon2.in と dragon/dragon2.ans を参照してください。
小課題
| テストケース番号 | $n$ | $m$ | $p_i$ | $a_i$ | 攻撃力 | その他の制約 |
|---|---|---|---|---|---|---|
| $1$ | $\leq 10^5$ | $=1$ | $=1$ | $\leq 10^5$ | $=1$ | なし |
| $2$ | $\leq 10^5$ | $=1$ | $=1$ | $\leq 10^5$ | $=1$ | なし |
| $3$ | $\leq 10^5$ | $=1$ | $=1$ | $\leq 10^5$ | $\leq 10^5$ | なし |
| $4$ | $\leq 10^5$ | $=1$ | $=1$ | $\leq 10^5$ | $\leq 10^5$ | なし |
| $5$ | $\leq 10^3$ | $\leq 10^3$ | $\leq 10^5$ | $\leq 10^5$ | $\leq 10^5$ | 性質 1、性質 2 |
| $6$ | $\leq 10^3$ | $\leq 10^3$ | $\leq 10^5$ | $\leq 10^5$ | $\leq 10^5$ | 性質 1、性質 2 |
| $7$ | $\leq 10^3$ | $\leq 10^3$ | $\leq 10^5$ | $\leq 10^5$ | $\leq 10^5$ | 性質 1、性質 2 |
| $8$ | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | 性質 1 |
| $9$ | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | 性質 1 |
| $10$ | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | 性質 1 |
| $11$ | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | 性質 1 |
| $12$ | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | 性質 1 |
| $13$ | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | 性質 1 |
| $14$ | $=10^5$ | $=10^5$ | $=1$ | $\leq 10^8$ | $\leq 10^6$ | 特別な制約なし |
| $15$ | $=10^5$ | $=10^5$ | $=1$ | $\leq 10^8$ | $\leq 10^6$ | 特別な制約なし |
| $16$ | $\leq 10^5$ | $\leq 10^5$ | すべての $p_i$ が素数 | $\leq 10^{12}$ | $\leq 10^6$ | 性質 1 |
| $17$ | $\leq 10^5$ | $\leq 10^5$ | すべての $p_i$ が素数 | $\leq 10^{12}$ | $\leq 10^6$ | 性質 1 |
| $18$ | $\leq 10^5$ | $\leq 10^5$ | 特別な制約なし | $\leq 10^{12}$ | $\leq 10^6$ | 性質 1 |
| $19$ | $\leq 10^5$ | $\leq 10^5$ | 特別な制約なし | $\leq 10^{12}$ | $\leq 10^6$ | 性質 1 |
| $20$ | $\leq 10^5$ | $\leq 10^5$ | 特別な制約なし | $\leq 10^{12}$ | $\leq 10^6$ | 性質 1 |
性質 1：任意の $i$ について、$a_i \leq p_i$ です。
性質 2：$\operatorname{LCM}(p_i) \leq 10^6$、すなわち、すべての $p_i$ の最小公倍数が $10^6$ 以下です。
すべてのテストケースで、$T \leq 5$、すべての武器の攻撃力は $10^6$ 以下、すべての $p_i$ の最小公倍数は $10^{12}$ 以下です。
ヒント
途中の計算結果が非常に大きくなることがあります。途中の結果を格納する変数の型に注意してください。