你正准备开车去上班。你要走的道路是一条没有限速的直线。然而，每隔一公里就有一个交通灯，你不能闯红灯。交通灯在绿灯和红灯之间瞬间切换，只要是绿灯，你就可以通过。你也可以在交通灯变色的那一刻通过。道路的起点和终点没有交通灯。

你的车很特别，它是一辆 iCar，第一辆橙色汽车，而且只有一个按钮。当你按住按钮时，汽车以 $1\text{m/s}^2$ 的恒定加速度加速；当你松开按钮时，汽车会立即停止。

你已经多次开车去上班，所以你碰巧知道交通灯的时间表。现在的问题是，你最快能多快到达目的地？

图片由 Les Chatfield 裁剪

输入格式

第一行包含一个整数 $n$，表示道路的长度（以公里为单位，$1 \le n \le 16$）。接下来的 $n - 1$ 行，每行包含 3 个整数 $t_i, g_i$ 和 $r_i$，分别表示第 $i$ 个交通灯在你开始开车后第一次从红灯变为绿灯的时间；绿灯持续时间和红灯持续时间（$40 \le g_i, r_i \le 50; 0 \le t_i < g_i + r_i$）。时间单位为秒。

你可以假设任何满足 $t_i > r_i$ 的交通灯在你开始开车时是绿灯，并在 $t_i - r_i$ 秒后变为红灯。

输出格式

输出到达道路终点所需的最短时间。相对误差或绝对误差在 $10^{-6}$ 以内的答案将被接受。

样例

样例输入 1

1

样例输出 1

44.72135955

样例输入 2

2
50 45 45

样例输出 2

68.52419365

样例输入 3

2
25 45 45

样例输出 3

63.2455532