小 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
第一組數據：
- 一開始擁有嘅劍嘅攻擊力係 $\{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 | $\leq 10^5$ | $=1$ | $=1$ | $\leq 10^5$ | $=1$ | 無 |
| 2 | ||||||
| 3 | $\leq 10^5$ | |||||
| 4 | ||||||
| 5 | $\leq 10^3$ | $\leq 10^3$ | $\leq 10^5$ | 特性 1、特性 2 | ||
| 6 | ||||||
| 7 | ||||||
| 8 | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | 特性 1 |
| 9 | ||||||
| 10 | ||||||
| 11 | ||||||
| 12 | ||||||
| 13 | ||||||
| 14 | $=10^5$ | $=10^5$ | $=1$ | 冇特別限制 | ||
| 15 | ||||||
| 16 | $\leq 10^5$ | $\leq 10^5$ | 所有 $p_i$ 都係質數 | $\leq 10^{12}$ | 特性 1 | |
| 17 | ||||||
| 18 | 冇特別限制 | |||||
| 19 | ||||||
| 20 |
特性 1 係指：對於任意嘅 $i$，$a_i\leq p_i$。
特性 2 係指：$\operatorname{LCM}(p_i)\leq 10^6$，即係所有 $p_i$ 嘅最小公倍數唔大過 $10^6$。
對於所有測試點，$T\leq 5$，所有武器嘅攻擊力 $\leq 10^6$，所有 $p_i$ 嘅最小公倍數 $\leq 10^{12}$。
提示
你用到嘅中間結果可能好大，要留意儲存中間結果嘅變數類型。