Fast Ride 
Time Limit: 1500ms, Special Time Limit:2500ms, Memory Limit:32768KB 
Total submit users: 3, Accepted users: 2 
Problem 10047 :
No special judgement

Problem description 
Is there a Russian who does not like a fast ride?! Royal messenger should get from point A to point B as quickly as possible. Point A has coordinate 0 on the Ox axis. Point B has positive coordinate B on the Ox
axis. Of course, the messenger will use horses to get to the
destination point. The messenger is not allowed to travel by foot
because of an importance of his mission and security reasons.
There are N stables on the straight line from A to B. The ith stable has M_{i} horses inside. Each horse is characterized by its speed v_{j} and maximum distance it can gallop d_{j}
(after that it falls exhausted). The messenger can change the horse
reaching or passing a stable to any horse from that stable without
losing time.
Your task is to find the minimum time the messenger needs to get to the point

Input 
The first line of the input contains two integer numbers B and N (1 ¡Ü B ¡Ü 10^{8}; 1 ¡Ü N ¡Ü 5000), where N is the number of stables. Descriptions of the stables follow. The first line of each description contains two integer numbers X_{i}, M_{i} (0 ¡Ü X_{i} ¡Ü 10^{8}; 0 < M_{i}) ?the position of the stable and the number of horses in this stable respectively. The following M_{i} lines contain the description of the horses. Each description of a horse is a pair of integer numbers v_{j}, d_{j} (1 ¡Ü v_{j} ¡Ü 10^{8}; 1 ¡Ü d_{j} ¡Ü 10^{8}). The total number of horses in all stables is no more than 10^{5}. It is possible that two or more stables have the same position.

Output 
Write the minimum time which will take the messenger to get to the point B to the output. The answer should be written with 3 digits after the decimal point. If the solution does not exist, write 1 to the output.

Sample Input 
10 3
5 2
1 100
10 3
0 1
1 50
8 1
2 3 
Sample Output 
6.300 
Problem Source 
SSU

Submit
Discuss
Judge Status
Problems
Ranklist
