Restoring Sequences

Little Ran had two positive integers \(x, y\) and two sequences of positive integers \(a = [a_1, a_2, \dots, a_n]\) and \(c = [c_1, c_2, \dots, c_n]\) satisfying the equations

\(a_i \times x + y = c_i\) for \(1 \le i \le n\).

Unfortunately, she forgot the values of \(y\) and the sequence \(a\). She only remembers \(x\) and the sequence \(c\). Your task is to restore one possible set of \(y\) and \(a\) satisfying the original equations. Since there might be many possible solutions, you are required to maximize the value of \(y\) and output this maximum \(y\) (note that you do not need to output the sequence \(a\)).

If no solution exists, output \(-1\) to indicate that.

Note: All formulas are rendered in \(\LaTeX\) format.

inputFormat

The first line contains two positive integers \(x\) and \(n\) where \(n\) is the length of the sequence \(c\). The second line contains \(n\) positive integers \(c_1, c_2, \dots, c_n\) separated by spaces.

outputFormat

Output a single integer, the maximum possible \(y\) such that there exists a sequence \(a\) of positive integers with \(a_i \times x + y = c_i\) for all \(1 \le i \le n\). If no solution exists, output \(-1\).

sample

3 3
10 13 16

7