iCar

You are at home and about to drive to work. The road is a straight line of $n$ kilometers with no speed limit. Traffic lights stand exactly every kilometer, so the $i$-th light is $i$ kilometers from your home ($1 \le i \le n-1$). There is no light at the start of the road and none at the end.

Your car has a single button. While you hold the button down, the car accelerates at a constant $1\,\mathrm{m/s^2}$. The moment you release the button the car stops on the spot and its speed drops to $0$, so pressing the button again starts the acceleration over from a standstill. You release the button only at a traffic light, and never in the middle of the road. At time $0$ the car stands still at the start of the road.

You cannot go past a red light. A light changes between green and red instantly, and passing a light exactly at the instant it changes colour is allowed. Waiting in front of a light while it is red is allowed. The instant you start moving again from a light is the instant you pass it, so the light has to be green at that instant.

You know the schedule of every light. How quickly can you reach the end of the road?

The first line contains one integer $n$, the length of the road in kilometers ($1 \le n \le 16$).

Each of the next $n-1$ lines contains three integers $t_i$, $g_i$ and $r_i$ describing the $i$-th light ($40 \le g_i, r_i \le 50$; $0 \le t_i < g_i + r_i$). Time $t_i$ is the first moment after you start driving at which that light switches from red to green, $g_i$ is the length of a green phase and $r_i$ is the length of a red phase. From $t_i$ on the light is green for $g_i$ seconds, then red for $r_i$ seconds, and this cycle repeats forever. The same cycle continues backwards in time before $t_i$. All times are in seconds.

A light with $t_i > r_i$ is therefore green at the moment you start driving and switches to red $t_i - r_i$ seconds later.

Print the minimum time in seconds needed to reach the end of the road, rounded to exactly six digits after the decimal point.