Bajtazar se acaba de mudar a un nuevo apartamento. Tras decorar sus estantes con los trofeos de varios concursos de recitación y campeonatos de canto tirolés de Bajtocia, se dio cuenta de que una pared estaba completamente vacía. Esto no le gustó, así que le gustaría llenarla con cuadros.

La pared de Bajtazar tiene forma rectangular con dimensiones $h \times w$ metros. Un marchante cercano, que es amigo íntimo de Bajtazar, ofrece $n$ tipos de cuadros, y dispone de una cantidad ilimitada de cuadros de cada tipo. Todos los cuadros del mismo tipo tienen exactamente las mismas dimensiones: los cuadros del tipo $i$ son siempre cuadrados con lados de longitud $d_i$ metros. Curiosamente, para cada par de valores distintos $d_i$, uno es divisible exactamente por el otro.

Para Bajtazar, el precio de los cuadros no importa (después de todo, los premios en los campeonatos de canto tirolés son bastante generosos), pero quiere asegurarse de que no quede ningún espacio vacío en la pared. Para ello, decidió comprar un cierto número de cuadros y colgarlos en la pared de tal manera que la cubran por completo. Por supuesto, los cuadros no pueden solaparse, pero pueden tocarse por los lados. Sin embargo, Bajtazar no quiere caminar demasiadas veces de ida y vuelta al marchante, por lo que le gustaría comprar la menor cantidad posible de cuadros. ¡Ayúdale y escribe un programa que calcule cuántos cuadros debe comprar, o que determine si cubrir la pared no es posible!

Entrada

La primera línea de la entrada contiene dos números enteros $h$ y $w$ ($1 \le h, w \le 10^9$) — las dimensiones de la pared de Bajtazar.

La segunda línea de la entrada contiene un número entero $n$ ($1 \le n \le 30$) — el número de tipos de cuadros.

La tercera línea de la entrada contiene una secuencia de $n$ números enteros distintos $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$; $d_i < d_{i+1}$; $d_{i+1}$ es divisible exactamente por $d_i$) — las dimensiones de los cuadros de cada tipo.

Salida

Si es posible cubrir la pared, la salida debe contener un único número entero en una línea, que represente el número mínimo posible de cuadros necesarios para cubrir la pared. En caso contrario, la línea debe contener el número $-1$.

Ejemplos

Entrada 1

6 10
3
1 3 6

Salida 1

9

Entrada 2

3 3
1
2

Salida 2

-1

Nota

En el primer caso de prueba, Bajtazar puede cubrir la pared con nueve cuadros (seis de tamaño $1 \times 1$, dos de tamaño $3 \times 3$ y uno de tamaño $6 \times 6$), por ejemplo, de la siguiente manera:

En el segundo caso de prueba, no es posible cubrir la pared exactamente.