小 D 最近在網上發現了一款小遊戲。遊戲的規則如下：
- 遊戲的目標是按照編號 $1\sim 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。
範例
輸入格式 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,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$。
第二組資料：
- 不存在既能殺死第一條龍又能殺死第二條龍的方法，故無法通關，輸出
-1。
範例 2
見選手目錄下的 dragon/dragon2.in 與 dragon/dragon2.ans。
子任務
| 測試點編號 | $n$ | $m$ | $p_i$ | $a_i$ | 攻擊力 | 其他限制 |
|---|---|---|---|---|---|---|
| $1,2$ | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | 無 |
| $3,4$ | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $\le 10^5$ | 無 |
| $5,6,7$ | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | 特性 1、特性 2 |
| $8,9,10,11,12,13$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | 特性 1 |
| $14,15$ | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | 無特殊限制 |
| $16,17$ | $\le 10^5$ | $\le 10^5$ | 所有 $p_i$ 是質數 | $\le 10^{12}$ | $\le 10^6$ | 特性 1 |
| $18,19,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}$。
說明
你所用到的中間結果可能很大，注意儲存中間結果的變數型別。