You are on holidays in the United States, in a highway in the middle of nothing (for instance, Ohio), driving one of those big cars where a whole football team would fit. Bored, you decide to discover what contanst speed you must mantain to reach the next petrol station as soon as possible. Remember: the greater the speed is, the greater the consumption is, so if when you arrive to the petrol station the car has still fuel, it means that you did not go fast enough [Footnote: OIE recommends a responsible driving in the real life.].

In particular, you know that your vehicle consumes

500 + ⌊ |
| ⌋ + ⌊ |
| ⌋ |

millilitres of fuel to go around a kilometre, where 0<*v*<30000 and −3000<*w*<3000 is the speed of the vehicle and the power of the wind
in centimetres per second, and the symbols ⌊ · ⌋ mean
round towards zero. (Certainly, these american cars consume a lot).

You are asked to, given the quantity of fuel that you have, the number of kilometres of distance to the petrol station, and the intensity of the wind in each one of the kilometres, say what speed in centimetres per second you should go all the travel to reach as soon as possible the petrol station, without being with no fuel during the travel.

**Input**

A test data contains various cases, separated by a line in white.
A case is described by various lines. The first one contains
two numbers *C*<10^{9} and *n*<10^{3}, separated by spaces, that
describe the quantity of fuel tha you have and the number of stretches
that separe you from the petrol station. The following *n* lines describe
a road stretch, formed by a pair of numbers *d*_{i} and *w*_{i},
with the length in kilometres and the power of the wind in the
*i*-th strecth. It is fulfilled that ∑_{i=1}^{n} *d*_{i} < 10^{5}. The consumption
of fuel in each kilometre of a stretch must be computed
individually, to avoid rounding problems.

**Output**

For each case, your program must print in a line the speed in centimetre per second that would allow you to reach before to the petrol station without being with no fuel during the travel. We assure you that this number is greater than 0 and less tan 30000.

**Hint:** Binary search is that invent that allow us to find
a word in the dictionary without reading all the words.

**Author:** Ricardo Martín, Omer Giménez.

Public test cases

**Input**

25329 3 7 -776 3 -627 1 -114 24208 3 5 -262 2 -676 1 -956 38454 5 2 -85 2 -840 3 -260 2 527 1 127

**Output**

10005 12115 14102

**Input**

5065527 6 147 -1552 61 -1254 94 -531 162 1940 101 -742 270 1034 5733043 1 512 166 3967428 6 118 -1803 71 -929 27 -981 140 372 3 322 420 -77

**Output**

18888 27923 17362

Information

- Author
- Omer Giménez
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++