题目描述

你准备从家开车去上班。道路是一条直线，没有限速，但每隔 $1$ 千米有一个红绿灯。红灯时不能通过，绿灯时可以通过；如果恰好在灯变色的瞬间通过，也视为允许。道路起点和终点没有红绿灯。

你的车是一辆特殊的 iCar，它只有一个按钮：

• 按住按钮时，汽车以 $1\ \mathrm{m/s^2}$ 的加速度匀加速；
• 松开按钮时，汽车会立刻停在当前位置。

你已经熟悉这条路上所有红绿灯的时间表。请计算最快多久能到达终点。

输入格式

第一行包含一个整数 $n$，表示道路长度，单位为千米，满足：

$$1 \le n \le 16.$$

接下来 $n-1$ 行描述第 $i$ 个红绿灯，即距离起点 $i$ 千米处的红绿灯。每行包含三个整数 $t_i,g_i,r_i$：

• $t_i$ 表示从你出发时刻之后，该灯第一次由红变绿的时间；
• $g_i$ 表示绿灯持续时间；
• $r_i$ 表示红灯持续时间。

满足：

$$40 \le g_i,r_i \le 50, \qquad 0 \le t_i < g_i+r_i.$$

时间单位为秒。

若 $t_i>r_i$，则该灯在出发时刻为绿灯，并会在 $t_i-r_i$ 秒后变红。

输出格式

输出到达终点所需的最短时间。

答案允许绝对误差或相对误差不超过 $10^{-6}$。

输入输出样例 #1

输入 #1

1

输出 #1

44.72135955

输入输出样例 #2

输入 #2

2
50 45 45

输出 #2

68.52419365

输入输出样例 #3

输入 #3

2
25 45 45

输出 #3

63.2455532