iCar

집에서 회사까지 가는 길은 속도 제한이 없는 직선 도로이고, 길이는 $n$킬로미터다. 신호등은 정확히 1킬로미터 간격으로 서 있어서 $i$번째 신호등은 집에서 $i$킬로미터 떨어져 있다($1 \le i \le n-1$). 출발점과 도착점에는 신호등이 없다.

차에는 버튼이 하나뿐이다. 버튼을 누르고 있는 동안 차는 $1\,\mathrm{m/s^2}$로 일정하게 가속한다. 버튼에서 손을 떼는 순간 차는 그 자리에서 즉시 멈추고 속도가 $0$이 되므로, 다시 누르면 정지 상태에서 가속을 새로 시작한다. 손은 신호등 위치에서만 뗀다. 도로 한가운데에서는 멈추지 않는다. 시각 $0$에 차는 도로 출발점에 정지해 있다.

빨간불인 신호등은 지나갈 수 없다. 불빛은 초록에서 빨강으로, 빨강에서 초록으로 순간에 바뀌며, 색이 바뀌는 바로 그 순간에 지나가는 것은 허용한다. 빨간불 동안 신호등 앞에서 기다려도 된다. 신호등에서 다시 출발하는 순간이 그 신호등을 지나가는 순간이므로, 그 순간의 불빛은 초록이어야 한다.

모든 신호등의 일정을 알고 있다. 도로 끝까지 가는 데 걸리는 최소 시간을 구하라.

첫 줄에 도로의 길이 $n$이 킬로미터 단위 정수로 주어진다($1 \le n \le 16$).

다음 $n-1$개 줄에는 $i$번째 신호등을 나타내는 세 정수 $t_i$, $g_i$, $r_i$가 주어진다($40 \le g_i, r_i \le 50$; $0 \le t_i < g_i + r_i$). $t_i$는 출발한 뒤 그 신호등이 처음으로 빨간불에서 초록불로 바뀌는 시각이고, $g_i$는 초록불이 이어지는 길이, $r_i$는 빨간불이 이어지는 길이다. $t_i$부터 $g_i$초 동안 초록불, 이어서 $r_i$초 동안 빨간불이고 이 주기가 계속 반복된다. $t_i$ 이전 시간에도 같은 주기가 거꾸로 이어진다. 시간 단위는 초다.

따라서 $t_i > r_i$인 신호등은 출발하는 순간에 초록불이고, $t_i - r_i$초 뒤에 빨간불로 바뀐다.

도로 끝에 도달하는 데 걸리는 최소 시간을 초 단위로, 소수점 아래 여섯 자리까지 반올림해 한 줄에 출력한다.