Velociraptors 201 P46713

You are going down in the lift of your home when you observe that the sensor of velociraptor flickers: it means that there is a velociraptor in the hall, waiting that the lift goes down to devour you. Other kind of person would cross his arms and would say that, Oh, well! This kind of things happen sometimes; luckely, you always bring the kit of self-defense against velociraptors that you bought in the home shopping service. When you open it, however, discover that the kit is just a plastic lance, in pieces, which instructions do not worth to follow because the whole lance will not fit in the lift. Ready, however, to defend the image of the human race, you are going to prepare the longest piece of lance that fits in the lift.

Kit is formed by $n$ pieces in the shape of a tube, each one of them has a length $l_i$ and a diameter $d_i$. the hooks of the pieces are such that you only can hook up a narrow tube in a wider one, so that the diameter of the result lance decreases every time you hook up a tube. In particular, you cannot hook up two tubes of the same diameter. You are asked to, given the maximal length $T$ that fits in the lift, and the lengths and diameters of the $n$ pieces, discover which is the lance of greatest lenght $t$ with $t\leq T$ that you can assemble.

Input

A test data contains various cases. Each case is described in various lines. The first one contains two naturals $T$ and $n$, with $1\leq T \leq 1000$ and $1 \leq n \leq 100$, that describe the maxinal size of lance that fits in the lift and the number of pieces. Then, $n$ lines come, each one with a pair of numbers $d_i$, $l_i$ separated by spaces, that describe the $n$ lengths and diameters in milimetres of the pieces. It is fulfilled that $1\leq d_i, l_i\leq 1000$.

Output

Your program must print for each case, the size $t$ of the maximal lance that fits in the lift and you can form using the pieces in the described way.

Scoring

• Test1:

  Solving a test data that contains 100 situations with $n \leq 15$, $T \leq 100$, and where the $d_i$ are different and are given in decreasing order of diameter (as in the instance 1).

• Test2:

  Solving a test data that contains 100 situations of all kinds.