Bajtazarは新しいアパートに引っ越したばかりです。朗読コンクールやバイトシアのヨーデル選手権で獲得したトロフィーを棚に飾った後、彼は壁が一つ完全に空いていることに気づきました。彼はそれが気に入らなかったので、絵画で壁を埋めたいと考えています。

Bajtazarの壁は $h \times w$ メートルの長方形です。Bajtazarの親しい友人である近くの画商は、$n$ 種類の絵画を提供しており、各種類の絵画は無制限に在庫があります。同じ種類の絵画はすべて全く同じ寸法であり、$i$ 番目の種類の絵画は常に一辺の長さが $d_i$ メートルの正方形です。興味深いことに、任意の異なる2つの値 $d_i, d_j$ について、一方は他方で割り切れます。

Bajtazarにとって絵画の価格は問題ではありません（ヨーデル選手権の賞金はかなり高額だからです）。しかし、彼は壁に隙間が残らないようにしたいと考えています。そのために、彼はある数の絵画を購入し、壁全体を覆うように配置することにしました。もちろん、絵画同士が重なってはいけませんが、辺で接することは可能です。Bajtazarは画商との往復を何度もしたくないため、購入する絵画の数を可能な限り少なくしたいと考えています。彼のために、購入すべき絵画の最小数を計算する、あるいは壁を覆うことが不可能であることを判定するプログラムを作成してください。

入力

入力の1行目には、Bajtazarの壁の寸法を表す2つの整数 $h$ と $w$ ($1 \le h, w \le 10^9$) が含まれます。

入力の2行目には、絵画の種類数である整数 $n$ ($1 \le n \le 30$) が含まれます。

入力の3行目には、$n$ 個の異なる整数の列 $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$; $d_i < d_{i+1}$; $d_{i+1}$ は $d_i$ で割り切れる) が含まれており、これらは各種類の絵画の寸法を表します。

出力

壁を覆うことが可能な場合、壁を覆うために必要な最小の絵画数を表す整数を1行に出力してください。不可能な場合は、$-1$ を出力してください。

入出力例

入力 1

6 10
3
1 3 6

出力 1

9

入力 2

3 3
1
2

出力 2

-1

注記

最初の例では、Bajtazarは9枚の絵画（$1 \times 1$ サイズを6枚、$3 \times 3$ サイズを2枚、$6 \times 6$ サイズを1枚）を使って、例えば以下のように壁を覆うことができます。

2番目の例では、壁を正確に覆うことは不可能です。