달아나는 메추라기

기르던 메추라기 $N$마리가 모두 달아났다. 당신은 수직선 위 좌표 $0$에 서 있고, $i$번째 메추라기는 $0$이 아닌 정수 좌표 $P_i$(미터)에서 출발한다. 메추라기는 매초 정수 속도 $S_i$미터로 당신에게서 멀어지는 방향으로 쉬지 않고 달리며, 당신이 자기 쪽으로 달려오지 않는 동안에도 계속 달린다. 당신은 매초 정수 속도 $Y$미터로 달릴 수 있고, 원하는 순간에 즉시 방향을 바꿀 수 있다. 당신이 어떤 메추라기와 같은 지점에 있게 되면 그 메추라기는 그 자리에서 잡히고, 잡는 데 추가 시간은 들지 않는다.

메추라기를 지나치려면 먼저 잡아야 하므로, 양의 좌표에서 출발한 메추라기는 계속 오른쪽으로, 음의 좌표에서 출발한 메추라기는 계속 왼쪽으로 달린다.

메추라기를 모두 잡는 데 걸리는 최소 시간은 몇 초인가?

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 당신의 속도 $Y$와 메추라기의 수 $N$이 공백을 두고 주어진다. 다음 줄에는 메추라기의 위치 $P_1, P_2, \dots, P_N$이, 그 다음 줄에는 메추라기의 속도 $S_1, S_2, \dots, S_N$이 각각 공백을 두고 주어진다.

제한

• $1 \le T \le 100$
• $2 \le Y \le 1000$
• $1 \le N \le 25$
• $-10^7 \le P_i \le 10^7$, $P_i \ne 0$
• $1 \le S_i < Y$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 메추라기를 모두 잡는 데 걸리는 최소 시간(초)이다.

$y$는 소수점 아래 여섯째 자리까지 반올림해서 적고, 소수점 아래 자리는 항상 여섯 개를 적는다. 버리는 부분이 정확히 절반이면 올린다. 입력 데이터의 정확한 답은 모두 반올림 경계에서 $10^{-9}$ 이상 떨어져 있다.

첫 번째 예제의 1번 테스트 케이스에서는 왼쪽으로 달려 출발 지점에서 왼쪽으로 12미터 떨어진 지점에서 메추라기 세 마리를 한꺼번에 잡을 수 있다. 3초가 걸린다.

2번 테스트 케이스의 최적 전략 하나는 다음과 같다. 먼저 왼쪽으로 달려 1초 뒤 좌표 $-2$에서 두 번째 메추라기를 잡고, 방향을 바꿔 오른쪽으로 달려 4초를 더 써서 좌표 $6$에서 첫 번째 메추라기를 잡는다.