Programming Puzzle: iCar

Here’s a programming puzzle I came up with. It was selected as one of eight problems in The 2015 Nordic Collegiate Programming Contest. The full set of problems for this competition can be found here and the solutions here.

You are at home and about to drive to work. The road you will take is a straight line with no speed limit. There are, however, traffic lights precisely every kilometer, and you can not pass a red light. The lights change instantaneously between green and red, and you can pass a light whenever it is green. You can also pass through a light at the exact moment of changing colour. There are no traffic lights at the start or the end of the road.

Now your car is special; it is an iCar, the first Orange car, and it has only one button. When you hold down the button, the car accelerates at a constant rate of 1 m/s²; when you release the button the car stops on the spot.

You have driven to work many times, so you happen to know the schedules of the traffic lights.

The problem

How quickly can you get to work?

Input

The first line contains a single integer n, the length of the road in kilometers (1 ≤ n ≤ 16). Each of the next n−1 lines contains 3 integers t_i, g_i and r_i, the first time the ith light will switch from red to green after the moment you start driving the car; the green light duration, and the red light duration (40 ≤ g_i, r_i ≤ 50; 0 ≤ t_i < g_i + r_i). Times are given in seconds.

You may assume that any light with t_i > r_i is green at the time you start driving the car, and switches to red t_i − r_i seconds later.

Output

Output the minimum time required to reach the end of the road. Answers within a relative or absolute error of 10⁻⁶ will be accepted.

Example

Example Input 1

Solution 1

44.72135955

Example Input 2

2
50 45 45

Solution 2

68.52419365

Example Input 3

2
25 45 45

Solution 3

63.2455532