Exact Measurement

Peter works in a chemistry laboratory. For a new experiment he must measure out exactly $x$ nanograms (ng) of a reagent. He has a balance and a collection of standard masses.

The masses are stored in $n$ sealed boxes. Box $i$ holds $q_i$ identical masses, each weighing $10^{k_i}$ ng. To take masses out of a box he must open it, and from an opened box he may take any number of its masses, from $0$ up to $q_i$.

Peter wants the total weight of the masses he takes to be exactly $x$ ng while opening as few boxes as possible. Determine the minimum number of boxes he must open.

The first line contains two integers $x$ and $n$ ($1 \le x \le 10^{18}$, $1 \le n \le 10^5$).

Each of the next $n$ lines contains two integers $k_i$ and $q_i$ describing one box ($0 \le k_i \le 18$, $1 \le q_i \cdot 10^{k_i} \le 10^{18}$).

Print a single integer: the minimum number of boxes Peter must open to measure exactly $x$ ng. If it is impossible to measure exactly $x$ ng, print $-1$.