Balloon Game

One of the joys of the university programming contest held every autumn in Daejeon is the balloon game. While waiting for the scoreboard to be revealed at the awards ceremony, bored contestants tie together the balloons around them to make a long balloon strand that stretches across the hall. Raising that strand into an arch over the podium is a chance to show off just how much free time one has.

Bored, Jaehyun and Hanpil brought a long balloon strand to play the balloon game. The strand has $N$ slots where balloons can be hung, numbered from $1$ to $N$. Hanpil attached balloons to the strand in $Q$ regular passes.

Each pass is described by two integers $L$ and $I$, meaning "starting at slot $L$, place a balloon on every slot whose number increases by $I$": that is, on slots $L, L+I, L+2I, \dots$ in order. Once the slot number would exceed $N$, that pass stops. If a slot already holds a balloon, it is skipped (no new balloon is placed there, and it stays filled).

After all $Q$ passes are finished, count how many slots are still empty.

The first line contains the number of slots $N$ and the number of passes $Q$. ($1 \le N \le 10,000$, $1 \le Q \le 100$)

Each of the next $Q$ lines describes one pass with two integers $L$ and $I$, meaning "starting at slot $L$, place balloons on the slots whose numbers increase by $I$". ($1 \le L, I \le N$)

Print the number of empty slots after all passes are finished.

The following shows the case $N = 30$ with three passes (this example is the same as the first test case below).

At first every slot is empty.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Placing balloons (R) with $L=1$, $I=3$ fills slots $1, 4, 7, \dots$

R . . R . . R . . R . . R . . R . . R . . R . . R . . R . .

Placing balloons (B) with $L=3$, $I=7$. Slots that are already filled (e.g. slot 10) are skipped.

R . B R . . R . . R . . R . . R B . R . . R . B R . . R . .

Placing balloons (D) with $L=1$, $I=4$.

R . B R D . R . D R . . R . . R B . R . D R . B R . . R D .

In the end, $13$ slots are empty.