Statement is not available in English language
B. Обратный путь
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Осьминог Сквидвард любит путешествовать по массиву. Сейчас он находится в ячейке $$$n$$$. Сквидвард очень хочет вернуться домой, который находится в ячейке $$$1$$$, для этого он хочет передвигаться прыжками по массиву. Осьминог умеет делать $$$m$$$ разных прыжков силой $$$k_i$$$. Прыжок силой $$$k_i$$$ перемещает его из ячейки $$$x$$$ в ячейку $$$\dfrac{x}{k_i}-1$$$ в том и только том случае, если $$$x$$$ делится без остатка на $$$k_i$$$.

За какое минимальное количество прыжков Сквидвард вернется домой?

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

В первой строке задано два целых числа $$$n$$$ и $$$m$$$ $$$(1 \leq n \leq 10^{12}, 1\leq m \leq 8)$$$  — ячейка, в которой находится осьминог, и количество вариантов прыжков, которые он может совершать.

Во второй строке заданы $$$m$$$ целых чисел $$$k_i$$$ $$$(1 \lt k_i\leq 100)$$$, разделённых пробелом,  — силы прыжков осьминога.

Гарантируется, что все $$$k_i$$$ различны.

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

В единственной строке выведите число – минимальное количество прыжков, за которое Сквидвард сможет вернуться домой, если он не сможет вернуться, выведите «-1» (без кавычек).

Примеры
Входные данные
55 3
2 3 5
Выходные данные
2
Входные данные
78 2
2 3
Выходные данные
-1