Exact Measurement

Time limit1sMemory limit128 MB

Summary

Each box offers up to q_i masses of weight 10^k_i; find the fewest boxes to open so the chosen masses sum to exactly x.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Math, Bit manipulation
Solved: No attempts yet

Problem

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.

Input

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}$ ).

Output

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$ .

Examples3

Example 1
Input
```
289 4
2 3
1 5
1 8
0 30
```
Expected output
```
3
```
Example 2
Input
```
300 4
2 3
1 5
1 7
0 30
```
Expected output
```
1
```
Example 3
Input
```
201 1
2 3
```
Expected output
```
-1
```