C :: Cycling

Time Limit: 3 Seconds    Memory Limit: 32768 KB

On a bicycle trip through the city, a significant amount of time is spent waiting for traffic lights. If only you could reduce this lost time, maybe you would finally manage to get to class in time for the first lecture.

Note that the amount of time lost on a red traffic light is more than just the time spent standing still at the light. After the light turns green, additional time is lost while the bicycle accelerates.

In this problem, we assume a theoretical model of a bicycle trip, based on the following rules: 

• The bicycle moves forward or stands still, but it never moves backwards. The bicycle does not have a maximum speed, but you may rest assured that relativistic effects will not be involved in this problem.

• The bicycle can increase speed at a maximum acceleration of 0.5 meters per second per second.

• The bicycle can instantaneously reduce its speed to any value between zero and the current speed.

• The bicycle cannot go through a red light.

• Each traffic light turns red and green according to a fixed, continuously repeating rhythm. (These traffic lights don’t turn yellow.)

It should be obvious that the theoretical model deviates from reality in several ways. For example, Dutch cyclists hardly ever stop for red lights. Also, the modelled bicycle can decelerate at an infinite rate, while most student’s bikes do not have any braking capability to speak of.

We ignore these differences for now and focus on the theory.

 

 

You are standing with your bike at point X = 0 at time T = 0 with zero speed. You are in an enormous hurry and would like to arrive at point X = Xdest as soon as possible.

 

Your task is to find a pattern of accelerating and braking such that you safely pass all traffic lights and arrive in Xdest at the earliest possible time.

It is allowed to brake and/or stop at any point during the trip, including (of course) for red traffic lights. However, it may be more efficient to figure out some way in which you can cycle past the traffic lights while they are green.

 

 

Input

The input for each test case consists of the following items:

• A line containing a floating point number Xdest and an integer L.

Xdest is the total distance to travel in meters (1 ≤ Xdest ≤ 10000);

L is the number of traffic lights to pass (0 ≤ L ≤ 10).

• L lines describing the traffic lights, listed in order of increasing X position.

Each of these lines contains 3 floating point numbers:

– Xi , the position of the traffic light in meters from the start (0 < Xi < Xdest );

– Ri , the duration of each red-light period of this traffic light in seconds (10 ≤ Ri ≤ 500);

– Gi , the duration of each green-light period of this traffic light in seconds (10 ≤ Gi ≤ 500).

All traffic lights turn red at time T = 0.

Traffic light i turns green for the first time at T = Ri .

There is never more than one traffic light in the same position.

 

Output

For each test case, write one line of output containing a floating point number: the earliest time at which the cyclist can reach the destination.

The answer should be rounded to 3 digits after the decimal point.

The test cases will be such that very small inaccuracies will not cause errors in the final answer after rounding.

 

Sample Input

410.0 2
200.0 15.0. 15.0
225.0 31.0 10.0
410.0 2
200.0 15.0 15.0
225.0 35.1 15.0
410.0 2
200.0 15.0 15.0
225.0 45.0 10.0

Sample Output

41.497
52.623
57.213
Submit

Source: NWERC 2012