연료가 바닥난 차

차의 연료가 떨어졌다. 최대한 빨리 집에 도착해야 한다. 다행히 집은 언덕 아래에 있고 당신의 차는 언덕 꼭대기에 있다. 문제는 바로 앞에 다른 차가 한 대 있어서 추월할 수 없다는 점이다. 대신 브레이크는 멀쩡하고 제동력이 아주 강하다.

시각 0초에 언덕 꼭대기에서 속도 0 m/s로 출발한다. 중력은 일정한 가속도로 차를 언덕 아래로 끌어내린다. 어느 시각에나 브레이크를 밟아 속도를 원하는 만큼 줄이거나 가속도를 잠시 원하는 만큼 줄일 수 있다.

브레이크를 가장 잘 사용했을 때 집에 도착하는 최소 시간을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 세 수 $D$, $N$, $A$가 공백으로 구분되어 주어진다. $D$는 언덕 꼭대기에서 집까지의 거리를 미터로 나타낸 실수이고 소수점 아래 6자리로 주어진다. $N$과 $A$는 정수이다.

다음 $N$개의 줄에는 두 실수 $t_i$와 $x_i$가 공백으로 구분되어 주어진다. $t_i$는 초 단위 시각, $x_i$는 미터 단위 위치이며 둘 다 소수점 아래 6자리로 주어진다. 시각 $t_i$에 앞차가 당신의 출발 지점에서 언덕 아래로 $x_i$미터 떨어진 곳에 있다는 뜻이다.

마지막 줄에는 $A$개의 실수 $a_i$가 공백으로 구분되어 주어진다. 각각 $\mathrm{m/s^2}$ 단위의 가속도이고 소수점 아래 2자리로 주어진다.

앞차는 시각 $t_i$와 $t_{i+1}$ 사이를 일정한 속도로 이동한다. 시각 $t_{N-1}$ 이후로는 언덕 위로 되돌아오지 않으므로 앞차의 위치는 계속 $x_{N-1}$ 이상이다.

예를 들어 $t_5 = 10$, $x_5 = 20$, $t_6 = 20$, $x_6 = 40$이면 출발 10초 뒤에 앞차는 20미터 아래에 있고, 15초 뒤에는 30미터 아래에, 20초 뒤에는 40미터 아래에 있다.

제한

• $1 \le T \le 20$
• $1.0 \le D \le 10^4$
• $1 \le N \le 1000$
• $1 \le A \le 10$
• $1.00 \le a_i \le 9.81$
• $0.0 \le t_i \le 10^5$
• $0.0 \le x_i \le 10^5$
• $t_0 = 0$, $t_i < t_{i+1}$
• $x_i < x_{i+1}$
• $x_{N-1} \ge D$

각 테스트 케이스마다 먼저 Case #c: 형식의 줄을 출력한다. $c$는 1부터 시작하는 테스트 케이스 번호이다. 그 다음 $A$개의 줄을 출력하며, $i$번째 줄에는 중력 가속도가 $a_i$일 때 집에 도착하는 최소 시간을 초 단위로 쓴다.

시간은 소수점 아래 일곱째 자리에서 반올림해 소수점 아래 정확히 6자리로 출력한다. 예를 들어 25초는 25.000000으로 쓴다. 빈 줄은 출력하지 않는다.

위치와 가속도. 가속도가 $a\ \mathrm{m/s^2}$로 일정하고 처음 속도가 $v_0\ \mathrm{m/s}$인 물체는 $t$초 동안 $v_0 t + \frac{1}{2} a t^2$만큼 이동한다.

경사면 위의 거리. 모든 거리와 가속도는 언덕을 따라 내려가는 직선 방향으로 잰다. 수평 거리가 아니다. 처음 속도가 $0\ \mathrm{m/s}$인 차가 $2\ \mathrm{m/s^2}$로 가속하고 앞차가 $x = 1$에 멈춰 있다면 정확히 1초 뒤에 앞차에 닿는다.

앞차. 앞차를 절대 추월할 수 없다. 어느 시각에도 당신이 내려온 거리가 앞차가 내려온 거리보다 클 수 없다. 두 거리가 같아도 된다. 두 차는 모두 질점으로 본다.

브레이크. 브레이크는 어느 시각에나 속도를 원하는 만큼 줄인다. 속도가 음수가 되는 일은 없다.