Bajtazar vừa chuyển đến căn hộ mới. Sau khi trang trí các kệ bằng những chiếc cúp từ nhiều cuộc thi ngâm thơ và giải vô địch hát yodel tốc độ của Bajtocja, anh nhận thấy một bức tường vẫn còn trống trơn. Anh không thích điều đó và muốn lấp đầy nó bằng những bức tranh.

Bức tường của Bajtazar có hình chữ nhật với kích thước $h \times w$ mét. Một người buôn tranh gần đó, vốn là bạn thân của Bajtazar, cung cấp $n$ loại tranh, với số lượng không giới hạn cho mỗi loại. Tất cả các bức tranh cùng loại đều có kích thước chính xác như nhau – tranh loại $i$ luôn là hình vuông với cạnh dài $d_i$ mét. Điều thú vị là với bất kỳ hai giá trị $d_i$ khác nhau nào, giá trị này luôn chia hết cho giá trị kia.

Đối với Bajtazar, giá thành của các bức tranh không thành vấn đề (dù sao thì giải thưởng tại các cuộc thi hát yodel tốc độ cũng khá lớn), tuy nhiên anh muốn đảm bảo rằng không còn bất kỳ khoảng trống nào trên tường. Để làm điều này, anh quyết định mua một số lượng tranh nhất định và treo chúng lên tường sao cho phủ kín hoàn toàn. Tất nhiên, các bức tranh không được chồng lên nhau, nhưng chúng có thể chạm cạnh nhau. Bajtazar không muốn đi lại giữa nhà mình và cửa hàng tranh quá nhiều lần – vì vậy anh muốn mua số lượng tranh ít nhất có thể. Hãy giúp anh ấy và viết một chương trình tính toán số lượng tranh tối thiểu mà anh ấy cần mua, hoặc xác định rằng việc phủ kín bức tường là không thể!

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $h$ và $w$ ($1 \le h, w \le 10^9$) – kích thước bức tường của Bajtazar.

Dòng thứ hai của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 30$) – số loại tranh.

Dòng thứ ba của dữ liệu vào chứa một dãy gồm $n$ số nguyên khác nhau $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$; $d_i < d_{i+1}$; $d_{i+1}$ chia hết cho $d_i$) – kích thước cạnh của các loại tranh theo thứ tự.

Dữ liệu ra

Nếu việc phủ kín bức tường là khả thi, hãy in ra một số nguyên duy nhất trên một dòng, biểu thị số lượng tranh tối thiểu cần thiết để phủ kín bức tường. Nếu không, hãy in ra số $-1$.

Ví dụ

Ví dụ 1

Dữ liệu vào:

6 10
3
1 3 6

Dữ liệu ra:

9

Ví dụ 2

Dữ liệu vào:

3 3
1
2

Dữ liệu ra:

-1

Ghi chú

Giải thích ví dụ: Trong ví dụ đầu tiên, Bajtazar có thể phủ kín bức tường bằng chín bức tranh (sáu bức kích thước $1 \times 1$, hai bức kích thước $3 \times 3$ và một bức kích thước $6 \times 6$), ví dụ như theo cách sau:

Trong ví dụ thứ hai, không thể phủ kín hoàn toàn bức tường.