달아난 메추라기

이런 -- 애완 메추라기 N마리가 모두 달아났다! 현재 당신은 직선 위의 위치 0에 있다. i번째 메추라기는 그 직선 위의 영이 아닌 정수(양수 또는 음수) 위치 $P_{i}$미터에서 출발하며, 초당 $S_{i}$미터의 일정한 정수 속도로 계속 당신에게서 달아난다. 당신은 초당 Y미터의 일정한 정수 속도로 달릴 수 있으며, 원할 때마다 즉시 방향을 바꿀 수 있다. 당시 당신이 메추라기를 향해 달리고 있지 않더라도 메추라기는 계속 당신에게서 달아난다는 점에 유의한다. 당신이 메추라기와 같은 지점에 있게 될 때마다 그 메추라기를 잡는다(여기에는 추가 시간이 들지 않는다).

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

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

2 ≤ Y ≤ 1000. -$10^{7}$ ≤ $P_{i}$ ≤ $10^{7}$; 어떤 $P_{i}$도 0이 아니다. 1 ≤ $S_{i}$ < Y.

작은 데이터 세트

시간 제한: 240초. 1 ≤ N ≤ 25.

큰 데이터 세트

시간 제한: 480초. 1 ≤ N ≤ 500.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 정수 Y와 N이 있는 한 줄로 시작한다. Y는 당신의 속도이고 N은 메추라기의 수이다. 그 뒤에는 각각 공백으로 구분된 N개의 정수가 있는 두 줄이 더 주어진다. 이 중 첫 번째 줄에는 메추라기의 위치 $P_{i}$가 주어지고, 두 번째 줄에는 속도 $S_{i}$가 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 모든 메추라기를 잡는 데 필요한 최소 시간(초)이다.

y의 절대 오차 또는 상대 오차가 정답의 10^{-6} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참조한다.

케이스 #1에서는 왼쪽으로 달려 출발 위치에서 왼쪽으로 12미터 떨어진 지점에서 세 마리의 메추라기를 동시에 모두 잡을 수 있으며, 여기에는 3초가 걸린다.

케이스 #2에서 가능한 최적 전략 중 하나는 왼쪽으로 달려 -2 m 지점에서 두 번째 메추라기를 잡는 것이다. 여기에는 일 초가 걸린다. 그런 다음 오른쪽으로 달려 첫 번째 메추라기를 추격하면 6 m 지점에서 잡게 되며, 추가로 사 초가 걸린다.