기름이 떨어진 언덕길 (큰 입력)

언덕 꼭대기에서 차의 기름이 떨어졌다. 집은 언덕 아래에 있으니 최대한 빨리 내려가고 싶다. 문제는 바로 앞에 다른 차가 한 대 있어서 그 차를 앞지를 수 없다는 것이다. 다행히 브레이크는 아주 잘 듣는다.

시각 $0$초에 언덕 꼭대기에서 속력 $0\ \text{m/s}$로 출발한다. 중력은 언덕을 따라 내려가는 방향으로 일정한 가속도를 준다. 어느 순간에나 브레이크를 밟아 속력을 줄이거나, 그 순간의 가속도를 원하는 만큼 줄일 수 있다.

브레이크를 가장 잘 썼을 때 집까지 걸리는 최소 시간을 구하라.

제약

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

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

각 테스트 케이스의 첫 줄에는 실수 $D$와 정수 $N$, $A$가 공백으로 구분되어 주어진다. $D$는 언덕을 따라 집까지 내려가야 하는 거리이고 단위는 미터이며, 소수점 아래 여섯 자리까지 주어진다.

다음 $N$개의 줄에는 각각 실수 $t_i$(초)와 $x_i$(미터)가 공백으로 구분되어 주어진다. $t_i$와 $x_i$도 소수점 아래 여섯 자리까지 주어진다.

그다음 줄에는 실수 $a_i$가 $A$개, 공백으로 구분되어 주어진다. 단위는 $\text{m/s}^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$번째 줄에는 중력에 의한 가속도가 $a_i$일 때 브레이크를 가장 잘 써서 집에 도착하는 최소 시간을 초 단위로 출력한다. 각 값은 소수점 아래 여섯 자리로 반올림해 정확히 여섯 자리를 출력한다. 출력에 빈 줄은 없다.

위치와 가속도. 일정한 가속도 $a\ \text{m/s}^2$와 초기 속력 $v_0\ \text{m/s}$로 움직이는 물체는 $t$초 동안 $v_0 t + \frac{1}{2} a t^2$만큼 이동한다.

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

앞차. 앞차를 절대 앞지를 수 없다. 즉 어느 시각에도 내가 내려온 거리가 앞차가 내려온 거리보다 클 수 없다. 두 거리가 같은 것은 괜찮다. 두 차는 모두 질점으로 본다.

마지막 점 이후. 앞차는 뒤로 가지 않고 $x_{N-1} \ge D$이므로, 시각 $t_{N-1}$ 이후의 앞차 위치는 나를 막지 않는다.