Minimum Production Runs

You are given an integer \(N\) representing the total number of widgets that need to be produced, and a list of \(m\) integers which denote the capacities of various production runs. Each production run can produce a fixed number of widgets as specified by the capacities list.

Your task is to determine the minimum number of production runs required to produce exactly \(N\) widgets. If it is not possible to produce exactly \(N\) widgets using any combination (repetition allowed) of the provided capacities, output \(-1\).

Formally, given an integer \(N\) and capacities \(c_1, c_2, \dots, c_m\), find the minimum number \(k\) such that there exist \(a_1, a_2, \dots, a_k \in \{c_1, c_2, \dots, c_m\}\) satisfying:

\[ a_1 + a_2 + \dots + a_k = N \]

If no such \(k\) exists, output \(-1\).

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains two integers: (N) (the required number of widgets) and (m) (the number of available production run capacities).
• The second line contains (m) space-separated integers representing the capacities of the production runs.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of production runs required to produce exactly (N) widgets. If it is not possible, output (-1).## sample

7 3
1 3 4

2

</p>