Description

The annual New Year party is coming soon. Xiao Ming, as the class monitor, is responsible for organizing and planning the event. He decides to purchase some prizes to reward students who actively participate in each activity. To encourage more participation, the number of prizes purchased should be as large as possible. The class fund can spend up to $m$ yuan. Given the prices and stock quantities of $n$ types of items available in the store, how can Xiao Ming buy the maximum number of items?

Input Format

The input consists of $n+1$ lines:
The first line contains two positive integers $m$ ($1< m \leq 10000$) and $n$ ($1 < n \leq 100$), representing the available budget and the number of types of items available for purchase.
The next $n$ lines each contain two numbers (separated by a space), representing the unit price $a$ and stock quantity $b$ of each item. Both $a$ and $b$ do not exceed $1000$.

Output Format

An integer representing the maximum number of items that can be purchased.

Sample

500 6
100 3
20 15
50 10
35 5
5 6
60 2

25