005 - 天秤

時間制限 8 秒 / メモリ制限 256 MB / 得点 20 / x 2 /


TLE
8sec
MLE
256MB
得点
20

問題

実験化学者のあなたは粉末薬品の計量用に天秤ひとつと分銅のセットを持っている.

作業効率上, 1 回の計量には天秤を 1 回使うだけにしたい. セット中の分銅は同時にいくつ使ってもよく, 天秤の薬品と反対側に置いても同じ側に置いてもよい. たとえば 2 単位と 9 単位の分銅があれば, 2 単位, 9 単位だけでなく, 薬品と反対側に両方の分銅を置けば 11 単位 (図 C-1 左), 片方を薬品と同じ側に置けば 7 単位の薬品を量り取ることができる (図 C-1 右). 効率的に量り取れる量はこれらだけである.

図 C-1 薬品 11 単位と 7 単位の計測法

手元に今日計量する薬品量のリストがある. しかし手持ちの分銅セットだけでは, 計量リスト中の量すべてを効率的に量れるとは限らない. その場合はもうひとつだけ分銅を買ってきて補ってもよいのだが, 重い分銅ほど高価なので, なるべく軽いもので済ませたい.

なお, どんな正の重さの分銅でも売っているが, 負の重さのものはない.

Input

入力は次の形式の最大 100 個のデータセットからなる.

n m
a1 a2 ... an
w1 w2 ... wm

データセットの最初の行の nm は, それぞれ計量リスト中の薬品量の数とセット中の分銅の個数である. これらは空白で区切られており, 1 ≤ n ≤ 100 と 1 ≤ m ≤ 10 を満たす整数である.

次の行には計量リスト中の n 種の量 a1 から an が空白区切りで並ぶ. 各 ai は 1 ≤ ai ≤ 109 を満たす整数で, ij ならば aiaj である.

データセットの最後の 3 行目には, 手持ちの m 個の分銅の重さ w1 から wm が空白区切りで並ぶ. 各 wj は 1 ≤ wj ≤ 108 を満たす整数である. 分銅は同じ重さのものがいくつもあるかもしれない.

入力の終わりはゼロふたつからなる行で表される.

Output

各データセットについて以下に指示する整数ひとつからなる 1 行を出力せよ.

  • 分銅を追加せずに計量リスト中のすべての量が量り取れるなら 0.
  • 分銅ひとつの追加で計量リスト中のすべての量が量り取れるようになるなら, そのような分銅のうちもっとも軽いものの重さ. 追加する分銅は 108 より重くてもよい.
  • 分銅ひとつの追加では計量リスト中のすべての量を量り取れるようにならないなら, -1.

Sample Input

4 2
9 2 7 11
2 9
6 2
7 3 6 12 16 9
2 9
5 2
7 3 6 12 17
2 9
7 5
15 21 33 48 51 75 111
36 54 57 93 113
0 0
  

Output for the Sample Input

0
5
-1
5