Байтазар только что переехал в новую квартиру. Украсив полки своими трофеями с различных конкурсов чтецов и чемпионатов Байтоции по скоростному йодлю, он заметил, что одна стена совершенно пуста. Ему это не понравилось, и он захотел заполнить её картинами.

Стена Байтазара имеет форму прямоугольника размером $h \times w$ метров. Местный торговец, который является близким другом Байтазара, предлагает $n$ видов картин, причём он располагает неограниченным количеством картин каждого вида. Все картины одного вида имеют абсолютно одинаковые размеры — картины $i$-го вида всегда являются квадратами со стороной длиной $d_i$ метров. Примечательно, что для любых двух различных значений $d_i$ одно делится нацело на другое.

Для Байтазара цена картин не имеет значения (в конце концов, награды на чемпионатах по скоростному йодлю довольно внушительны), однако он хотел бы убедиться, что на стене не останется ни одного пустого места. Для этого он решил купить некоторое количество картин и повесить их на стену так, чтобы полностью её закрыть. Разумеется, картины не могут перекрывать друг друга, но могут соприкасаться сторонами. Байтазар не хочет слишком часто ходить к торговцу туда и обратно, поэтому он хотел бы купить как можно меньше картин. Помогите ему и напишите программу, которая вычислит, сколько картин он должен купить, или определит, что покрытие стены невозможно!

Входные данные

В первой строке входных данных находятся два целых числа $h$ и $w$ ($1 \le h, w \le 10^9$) — размеры стены Байтазара.

Во второй строке входных данных находится одно целое число $n$ ($1 \le n \le 30$) — количество видов картин.

В третьей строке входных данных находится последовательность из $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

Входные данные:

6 10
3
1 3 6

Выходные данные:

9

Пример 2

Входные данные:

3 3
1
2

Выходные данные:

-1

Примечание

Пояснение к первому примеру: В первом тестовом примере Байтазар может покрыть стену девятью картинами (шестью размером $1 \times 1$, двумя размером $3 \times 3$ и одной размером $6 \times 6$), например, следующим образом:

Во втором тестовом примере точное покрытие стены невозможно.