자전거

도시에서 자전거를 탈 때, 교통 신호를 기다리는 시간은 전체 이동 시간에서 큰 비중을 차지한다. 자전거로 더 빨리 이동하려면 이 시간을 줄여야 한다.

신호 때문에 낭비되는 시간은 단순히 빨간불을 기다리는 시간만이 아니다. 초록불로 바뀐 뒤에 자전거를 다시 가속하는 데에도 시간이 들기 때문이다.

자전거의 움직임을 다음과 같이 모델링한다.

• 자전거는 앞으로 나아가거나 제자리에 멈춰 있을 수 있으며, 뒤로는 갈 수 없다. 최대 속도 제한은 없다.
• 자전거의 가속도는 최대 $0.5\,\mathrm{m/s^2}$ 이다. (매초 최대 $0.5\,\mathrm{m/s}$ 만큼 속도를 높일 수 있다.)
• 자전거는 현재 속도 이하의 임의의 속도($0$ 포함)로 즉시 감속할 수 있다.
• 빨간불인 신호등은 통과할 수 없다. 즉 그 위치에서는 빨간불 동안 앞으로 나아갈 수 없다.
• 각 신호등은 빨간불과 초록불이 일정한 주기로 번갈아 바뀐다. (노란불은 없다.)

이 모델은 이론적인 것으로 실제 현상과는 차이가 있다.

라이더는 시간 $T = 0$에 위치 $X = 0$에서 속도 $0$으로 정지해 있다. 목적지 $X = X_{dest}$까지 최대한 빨리 도착하려고 한다. 모든 신호등을 초록불일 때에만 통과하면서 $X_{dest}$에 도착할 수 있는 가장 빠른 시간을 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 파일의 끝까지 각 테스트 케이스를 처리한다.

각 테스트 케이스의 첫째 줄에는 목적지의 좌표 $X_{dest}$와 신호등의 개수 $L$이 주어진다. ($1 \le X_{dest} \le 10000$, $0 \le L \le 10$)

이어지는 $L$개의 줄에는 신호등 정보가 $X$좌표가 증가하는 순서로 주어진다. 각 줄에는 신호등의 위치 $X_i$ ($0 < X_i < X_{dest}$), 빨간불이 지속되는 시간 $R_i$ ($10 \le R_i \le 500$), 초록불이 지속되는 시간 $G_i$ ($10 \le G_i \le 500$)가 주어진다.

모든 신호등은 $T = 0$에 빨간불로 시작하며, 신호등 $i$는 $T = R_i$에 처음으로 초록불이 된다. 그 후 초록불이 $G_i$초 동안 유지되었다가 다시 빨간불로 바뀌며, 이 주기가 반복된다.

두 신호등이 같은 위치에 있는 경우는 없다. 모든 값은 실수일 수 있다.

각 테스트 케이스마다, 목적지에 도착할 수 있는 가장 빠른 시간을 소수점 셋째 자리까지 반올림하여 한 줄에 출력한다.