小 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。

子任務

特性 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}$。

提示

你用到嘅中間結果可能好大，要留意儲存中間結果嘅變數類型。