Bajtazar vient d'emménager dans un nouvel appartement. Après avoir décoré ses étagères avec ses trophées de divers concours de récitation et des championnats de yodel de Bajtocja, il a remarqué qu'un mur était complètement vide. Cela ne lui a pas plu, il souhaite donc le recouvrir de tableaux.

Le mur de Bajtazar est un rectangle de dimensions $h \times w$ mètres. Un marchand local, qui est un ami proche de Bajtazar, propose $n$ types de tableaux, et il dispose d'un nombre illimité de tableaux de chaque type. Tous les tableaux d'un même type ont exactement les mêmes dimensions : les tableaux du $i$-ième type sont toujours des carrés de côté $d_i$ mètres. Fait intéressant, pour deux valeurs différentes $d_i$, l'une est toujours divisible par l'autre sans reste.

Pour Bajtazar, le prix des tableaux n'a pas d'importance (après tout, les prix aux championnats de yodel sont assez conséquents), mais il veut s'assurer qu'aucun espace vide ne reste sur le mur. À cette fin, il a décidé d'acheter un certain nombre de tableaux et de les accrocher au mur de manière à le recouvrir entièrement. Bien sûr, les tableaux ne peuvent pas se chevaucher, mais ils peuvent se toucher par leurs côtés. Cependant, Bajtazar ne veut pas faire trop d'allers-retours chez le marchand ; il souhaite donc acheter le moins de tableaux possible. Aidez-le et écrivez un programme qui calcule pour lui combien de tableaux il doit acheter, ou indiquez si le recouvrement du mur n'est pas possible !

Entrée

La première ligne de l'entrée contient deux entiers $h$ et $w$ ($1 \le h, w \le 10^9$) — les dimensions du mur de Bajtazar.

La deuxième ligne de l'entrée contient un entier $n$ ($1 \le n \le 30$) — le nombre de types de tableaux.

La troisième ligne de l'entrée contient une séquence de $n$ entiers distincts $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$ ; $d_i < d_{i+1}$ ; $d_{i+1}$ est divisible par $d_i$ sans reste) — les dimensions des tableaux des types successifs.

Sortie

Si le recouvrement du mur est possible, la sortie doit contenir un seul entier sur une ligne, représentant le nombre minimal possible de tableaux nécessaires pour recouvrir le mur. Sinon, ce nombre doit être $-1$.

Exemples

Entrée 1

6 10
3
1 3 6

Sortie 1

9

Entrée 2

3 3
1
2

Sortie 2

-1

Remarque

Dans le premier exemple, Bajtazar peut recouvrir le mur avec neuf tableaux (six de taille $1 \times 1$, deux de taille $3 \times 3$ et un de taille $6 \times 6$), par exemple de la manière suivante :

Dans le deuxième exemple, il n'est pas possible de recouvrir le mur exactement.