005 - 天秤

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

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

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

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

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

n m
a₁ a₂ ... a_n
w₁ w₂ ... w_m

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

次の行には計量リスト中の n 種の量 a₁ から a_n が空白区切りで並ぶ. 各 a_i は 1 ≤ a_i ≤ 10⁹ を満たす整数で, i ≠ j ならば a_i ≠ a_j である.

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

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

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

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

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
  

0
5
-1
5