Special Brick Moving

Little E has a unique method of moving bricks. There are \(n\) stacks of bricks in front of him and his initial energy is \(d\). In each hour, he removes the top \(d\) bricks from every non-empty stack. If a stack has fewer than \(d\) bricks, he moves all the bricks in that stack.

Each stack has an associated parameter \(b\). When Little E completely clears a stack in an hour (i.e. when the number of bricks in a stack becomes less than or equal to \(d\) in that hour), his energy decreases by \(b\) immediately after that hour.

After finishing an hour, if at least one stack has been cleared, he feels happy and continues to work for another hour. However, if in any hour he does not clear any stack completely, he stops working.

If at the start of an hour all the bricks have already been moved, Little E will still work that hour in another way and it will count as a working hour. Also, if his energy drops to \(0\) or below, he stops working immediately.

Given the initial energy \(d\) and the details of \(n\) stacks (each with a number of bricks and an energy reduction \(b\) when cleared), determine how many consecutive hours Little E can work.

inputFormat

The first line contains two integers \(d\) and \(n\) \(\,(1 \le d \le 10^9,\, 1 \le n \le 10^5)\). Each of the following \(n\) lines contains two integers \(a\) and \(b\) \(\,(1 \le a, b \le 10^9)\), where:

• \(a\) is the number of bricks in the stack.
• \(b\) is the energy reduction if the stack is completely cleared in an hour.

outputFormat

Output a single integer representing the number of consecutive hours Little E can work.

sample

10 2
15 3
8 5

3