군마 2: 순항 제어

Annie는 스트레스가 심한 직업을 가진 버스 운전사이다. 긴장을 풀기 위해 카리브해 유람선 여행을 떠났지만 그 역시 스트레스가 심한 것으로 드러났고, 그래서 최근에는 승마를 시작했다.

오늘 Annie는 서쪽에서 동쪽으로 뻗은 길고 좁은 일방통행 도로를 따라 말을 타고 동쪽으로 가고 있다. 현재 도로의 0킬로미터 지점에 있으며, 목적지는 D킬로미터 지점이다. 도로의 킬로미터 지점 번호는 서쪽에서 동쪽으로 매겨져 있다.

같은 도로에서 동쪽으로 이동하는 다른 말이 N마리 있다. 이 말들은 모두 영원히 계속 이동하며, 현재 모두 Annie의 말과 목적지 사이에 있다. 이 말들 중 i번째 말은 처음에 $K_{i}$킬로미터 지점에 있고, 시간당 $S_{i}$킬로미터의 최대 속도로 이동하고 있다.

말들은 매우 예의 바르므로, 말 $H_{1}$은 자신보다 앞에서 출발한 다른 말 $H_{2}$을 추월(앞으로 지나감)하지 않는다. $H_{1}$보다 앞에서 출발한 말이 그 대상이다. (둘 이상의 말이 얼마 동안이든 같은 위치에 있을 수 있으며, 말은 하나의 점으로 간주해도 된다.) Annie의 말을 제외한 말들은 최대 속도로 이동하지만, 말 $H_{1}$이 더 느린 다른 말 $H_{2}$을 따라잡을 때마다 $H_{1}$은 $H_{2}$의 속도에 맞추도록 속도를 줄인다.

반면 Annie의 말에는 최대 속도가 없으며, 다른 말을 추월하지 않는 한 Annie가 선택한 어떤 속도로든 이동할 수 있다. 자신과 말이 편안하게 달릴 수 있도록 Annie는 현재 위치에서 목적지까지의 전체 여정에서 다른 어떤 말도 추월하지 않도록, 자신의 말에 적용할 하나의 일정한 "순항 제어" 속도를 선택하려 한다. 선택할 수 있는 그러한 속도의 최댓값은 얼마인가?

제한

1 ≤ T ≤ 100. 모든 i에 대해, 0 < $K_{i}$ < D ≤ $10^{9}$. 모든 i ≠ j에 대해, $K_{i}$ ≠ $K_{j}$. (어떤 두 말도 같은 위치에서 출발하지 않는다.) 1 ≤ $S_{i}$ ≤ 10000. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 2.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어지고, 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 D와 N으로 시작한다. D는 모든 말의 목적지 위치(킬로미터)이고, N은 도로 위에 있는 다른 말의 수이다. 이어서 N개의 줄이 주어진다. 이 중 i번째 줄에는 두 정수 $K_{i}$와 $S_{i}$가 주어진다. 이들은 도로 위에 있는 다른 말 중 i번째 말의 초기 위치(킬로미터)와 최대 속도(킬로미터/시간)이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, y는 Annie가 다른 말과 충돌하지 않고 사용할 수 있는 최대 일정 속도(킬로미터/시간)이다. y는 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ을 참고하라.

예제 케이스 #1에서는 도로 위에 다른 말이 한 마리 있으며, 이 말은 매우 느리다! 이 말은 25시간 후에 Annie의 목적지에 도착한다. 시간당 101킬로미터보다 빠른 어떤 속도라도 Annie가 목적지에 도착하기 전에 그 말을 추월하게 만든다.

예제 케이스 #2에서는 도로 위에 다른 말이 두 마리 있다. 더 빠른 말은 2시간 후 240킬로미터 지점에서 더 느린 말을 따라잡는다. 그러면 두 말은 1시간을 더 느린 말의 속도로 이동하여, 300킬로미터 지점에 있는 Annie의 목적지에 도착한다. Annie가 다른 말을 추월하지 않고 선택할 수 있는 최대 속도는 시간당 100킬로미터이다.