Bicycle

When riding a bicycle in a city, the time spent waiting at traffic lights makes up a large part of the total travel time. To get somewhere faster, this time must be reduced.

The time wasted because of traffic lights is more than just the time spent waiting at a red light: after the light turns green, it also takes time to accelerate the bicycle back up to speed.

The motion of the bicycle is modelled as follows.

• The bicycle can move forward or stay in place; it can never move backward. There is no maximum speed.
• The bicycle can accelerate by at most $0.5,\mathrm{m/s^2}$ (its speed can increase by at most $0.5,\mathrm{m/s}$ each second).
• The bicycle can instantly decelerate to any speed between $0$ and its current speed.
• The bicycle cannot pass a traffic light while it is red, i.e. it cannot move forward at that position during a red light.
• Each traffic light alternates between red and green with a fixed period. (There is no yellow light.)

This is a theoretical model and differs from real-world behaviour.

A rider starts at rest (speed $0$) at position $X = 0$ at time $T = 0$ and wants to reach the destination $X = X_{dest}$ as quickly as possible. Passing every traffic light only while it is green, find the earliest possible time to arrive at $X_{dest}$.

The input consists of several test cases; process test cases until end of file.

The first line of each test case contains the destination coordinate $X_{dest}$ and the number of traffic lights $L$ ($1 \le X_{dest} \le 10000$, $0 \le L \le 10$).

The following $L$ lines describe the traffic lights in order of increasing $X$ coordinate. Each line contains the light's position $X_i$ ($0 < X_i < X_{dest}$), the duration $R_i$ for which it stays red ($10 \le R_i \le 500$), and the duration $G_i$ for which it stays green ($10 \le G_i \le 500$).

Every traffic light starts red at $T = 0$; light $i$ turns green for the first time at $T = R_i$. It then stays green for $G_i$ seconds, turns red again, and this cycle repeats.

No two traffic lights share the same position. All values may be real numbers.

For each test case, print on its own line the earliest time at which the destination can be reached, rounded to three decimal places.