P1658 Shopping

You are going shopping. You have $N$ types of coins with different denominations, and each type is available in unlimited quantity. For convenience, you want to carry as few coins as possible, while still being able to form any value from $1$ to $X$.

The first line contains two integers $X, N$. The next $N$ integers denote the denomination of each coin type.

Output the minimum number of coins you need to carry. If there is no solution, output `-1`.

For 30% of the testdata, $N \le 3$, $X \le 20$. For 100% of the testdata, $N \le 10$, $X \le 10^3$. Translated by ChatGPT 5