시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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

교통 신호 때문에 낭비하는 시간은 빨간불을 기다리는 시간보다 더 많은 시간을 포함한다. 불이 초록불로 바뀌었을 때, 자전거를 가속하는 시간도 필요하기 때문이다.

자전거 여행을 아래와 같이 모델링할 수 있다.

  • 자전거는 앞으로 가거나 그 자리에 서있을 수 있다. 뒤로는 갈 수 없다. 자전거는 최대 속도가 없다. 
  • 자전거는 1초에 최대 초속 0.5미터 만큼 가속할 수 있다. (가속도가 최대 0.5m/s^2 이다)
  • 자전거는 현재 속도와 0 사이의 속도중 하나로 즉시 감속할 수 있다.
  • 자전거는 빨간불일 때 앞으로 갈 수 없다.
  • 신호등은 빨간불과 초록불이 번갈아가면서 특정 주기를 가지고 바뀐다. (노란불로 바뀌지 않는다)

위의 모델은 이론상의 모델로 실제 현상과는 많이 다르다.

상근이는 시간 T= 0에 점 X = 0에 속도 0으로 서있다. 상근이는 자전거를 타고 X=Xdest에 최대한 빨리 도착하려고 한다. 모든 신호등을 안전하게 통과하고 Xdest에 최대한 빠르게 도착하는 가속과 감속 패턴을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 도착지의 좌표 Xdest와 신호등의 개수 L이 주어진다. (1 ≤ Xdest ≤ 10000, 0 ≤ L ≤ 10)

다음 L개 줄에는 신호등의 정보가 X좌표가 증가하는 순으로 주어진다. 신호등 정보는 신호등의 위치 Xi (0 < Xi < Xdest), 빨간색이 지속되는 시간 Ri (10 ≤ Ri ≤ 500), 초록불이 지속되는 시간 Gi (10 ≤ Gi ≤ 500)로 이루어져 있따.

모든 신호등은 T = 0일때, 빨간불로 바뀌었다. 또, 신호등 i는 T = Ri일 때, 처음으로 초록불이 된다.

두 신호등이 같은 장소에 있는 경우는 없다.

출력

각 테스트 케이스에 대해서, 도착지에 도착하는 가장 빠른 시간을 소수점 세째 짜리로 반올림해 출력한다. 

예제 입력

410.0 2
200.0 15.0 15.0
225.0 31.0 10.0
410.0 2
200.0 15.0 15.0
225.0 35.1 15.0
410.0 2
200.0 15.0 15.0
225.0 45.0 10.0

예제 출력

41.497
52.623
57.213

힌트