# The one of the binary search P89178

Statement

html

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 + ⌊
 v+w 10
⌋ + ⌊
 (v+w)2 100000

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<109 and n<103, 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 di and wi, with the length in kilometres and the power of the wind in the i-th strecth. It is fulfilled that ∑i=1n di < 105. 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++