Making Change

Sue is waiting in line at a grocery store. Being in a hurry, she wants to pay with exact change when she reaches the front of the line. She does not yet know exactly how much her items will cost; she only knows an upper bound $C$ on their total cost.

Given the coins in Sue's pocket (each denomination and how many of that denomination she has), determine the minimum number of coins she must take out in advance so that she can pay exact change for every amount from $1$ to $C$.

Here, "taking out" a set of coins means selecting some coins ahead of time; for each amount from $1$ to $C$, she must be able to choose a subset of the taken-out coins whose values sum to exactly that amount.

The input contains multiple test cases.

Each test case begins with a line containing two integers $C$ and $m$ ($1 \le C \le 10^9$, $1 \le m \le 1000$), where $C$ is the maximum amount for which Sue must be able to make change, and $m$ is the number of distinct coin denominations she has.

Each of the next $m$ lines contains two integers $v_i$ and $n_i$ ($1 \le v_i \le 1000$, $1 \le n_i \le 1000$), where $v_i$ is the value of the $i$-th denomination and $n_i$ is the number of coins of that denomination Sue has.

The input is terminated by a line containing a single $0$, which should not be processed.

For each test case, print a single line containing the minimum number of coins Sue must take out so that she can make exact change for every amount from $1$ to $C$.

If no selection of her coins can cover every amount, print "Not possible" instead.