Осьминог Сквидвард любит путешествовать по массиву. Сейчас он находится в ячейке $$$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 32 3 5
2
78 22 3
-1
