연료 부족

자동차의 연료가 떨어졌고, 가능한 한 빨리 집에 가고 싶다! 다행히 집은 언덕 아래에 있고, 당신은 (자동차를 타고) 언덕 위에 있다. 불행히도 앞에 다른 자동차가 있으며, 그 자동차를 추월할 수 없다. 다행히 브레이크는 작동하며 성능이 매우 강력하다.

당신은 0초에 언덕 위에서 속도 0 m/s로 출발한다. 중력은 일정한 가속도로 자동차를 언덕 아래로 끌어당긴다. 언제든지 브레이크를 사용해 속도를 임의의 양만큼 줄이거나, 가속도를 일시적으로 임의의 양만큼 줄일 수 있다.

브레이크를 가능한 최선의 방법으로 사용한다면 얼마나 빨리 집에 도착할 수 있는가?

제한

메모리 제한: 1GB. 1 ≤ T ≤ 20. 1.0 ≤ D ≤ $10^{4}$. 1.0 ≤ $a_{i}$ ≤ 9.81. 0.0 ≤ $t_{i}$ ≤ $10^{5}$. 0.0 ≤ $x_{i}$ ≤ $10^{5}$. $t_{i}$ < $t_{i+1}$. $x_{i}$ < $x_{i+1}$. $t_{0}$ = 0 $x_{N-1}$ ≥ D.

테스트 세트 1 (Visible Verdict)

시간 제한: 60초. 1 ≤ N ≤ 2. 1 ≤ A ≤ 10.

테스트 세트 2 (Hidden Verdict)

시간 제한: 120초. 1 ≤ N ≤ 2000. 1 ≤ A ≤ 250.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 공백으로 구분된 세 수가 주어진다. 실수 D는 언덕 아래에 있는 집까지의 거리를 미터 단위로 나타내며, 나머지 두 수 N과 A는 정수이다. 거리 D는 정확히 소수점 이하 6자리로 주어진다.

이어서 N개의 줄이 주어지며, 각 줄에는 공백으로 구분된 두 실수가 주어진다. 하나는 초 단위의 시간 $t_{i}$이고, 다른 하나는 미터 단위의 위치 $x_{i}$이다. $t_{i}$ 값과 $x_{i}$ 값은 정확히 소수점 이하 6자리로 주어진다.

이어서 한 줄에 공백으로 구분된 A개의 실수 $a_{i}$가 주어지며, 이들은 m/s^{2} 단위의 가속도이다. 가속도는 정확히 소수점 이하 2자리로 주어진다.

다른 자동차의 위치는 ($t_{i}$, $x_{i}$) 쌍으로 명시된다. 시간 $t_{i}$초일 때 자동차의 위치는 언덕 위(즉, 당신의 초기 위치)에서부터 측정하여 $x_{i}$미터이다. 자동차는 시간 $t_{i}$와 $t_{i+1}$ 사이에서 일정한 속도로 이동한다. 위치와 시간은 모두 증가하는 순서로 주어지며, $t_{0}$=0이다.

예를 들어, $t_{5}$=10, $x_{5}$=20, $t_{6}$=20, $x_{6}$=40라면, 출발하고 10초 후에 다른 자동차는 언덕 아래로 20미터 떨어진 곳에 있고, 출발하고 15초 후에는 언덕 아래로 30미터 떨어진 곳에 있으며, 출발하고 20초 후에는 언덕 아래로 40미터 떨어진 곳에 있다.

각 테스트 케이스마다 "Case #c:"를 포함하는 한 줄을 출력한다. 여기서 c는 1부터 시작하는 케이스 번호이다. 그런 다음 A개의 줄을 출력하며, 그중 $i^{th}$에는 중력으로 인해 언덕 아래 방향으로 작용하는 가속도가 $a_{i}$이고 브레이크를 가능한 최선의 방법으로 사용할 때 집에 도착하는 데 걸리는 최소 초 수를 출력한다. 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내인 답은 정답으로 인정된다. 출력에 빈 줄이 있어서는 안 된다.

위치와 가속도: 가속도가 일정하게 a m/s^{2}이고 초기 속도가 v_{0} m/s인 물체는 t초 동안 $v_{0}$t + 0.5a*$t^{2}$after만큼 이동한다.

경사면에서의 거리: 모든 거리와 가속도는 언덕 아래로 향하는 직선을 기준으로 주어진다. 예를 들어 수평 거리가 아니다. 따라서 자동차가 초기 속도 0 m/s에서 2 m/s^{2}의 가속도로 움직이고 다른 자동차가 x=1에서 정지해 있다면, 다른 자동차에 도달하는 데 정확히 1초가 걸린다.

다른 자동차: 다른 자동차를 절대로 추월할 수 없다. 즉, 어느 때에도 언덕 아래로 이동한 당신의 거리가 다른 자동차의 거리보다 커서는 안 된다. 같아도 된다. 자동차들은 점 질량으로 간주해야 한다.

출력값: 출력에는 원하는 만큼 많은 소수점 이하 자릿수를 출력할 수 있다. 우리는 답을 읽어 우리의 답과 비교하며, 그때 부정확성의 임계값으로 10^{-6}을 사용한다. 따라서 우리의 관점에서는 25, 25.0, 25.000000이 같다. 소수점 뒤의 후행 영은 중요하지 않다.