준마 2: 순항 속도 (Small)

애니는 스트레스가 심한 버스 기사다. 기분을 풀려고 카리브해 크루즈 여행을 다녀왔지만 그마저도 스트레스였고, 그래서 최근에 승마를 시작했다.

오늘 애니는 서쪽에서 동쪽으로 이어지는 좁고 긴 일방통행 도로를 따라 말을 타고 동쪽으로 간다. 지금 위치는 도로의 0킬로미터 지점이고 목적지는 $D$킬로미터 지점이다. 도로의 킬로미터 표시는 서쪽에서 동쪽으로 커진다.

같은 도로를 동쪽으로 달리는 말이 $N$마리 더 있다. 이 말은 모두 멈추지 않고 계속 달리며, 지금은 모두 애니의 말과 목적지 사이에 있다. $i$번째 말은 처음에 $K_i$킬로미터 지점에 있고 최고 속도는 시속 $S_i$킬로미터다.

말은 매우 예의가 바르다. 말 $H_1$은 자기보다 앞에서 출발한 말 $H_2$를 추월하지 않는다. 두 마리 이상이 같은 위치에 얼마든지 오래 함께 있을 수 있고, 말은 크기가 없는 점으로 본다. 애니의 말을 뺀 나머지 말은 항상 최고 속도로 달리지만, $H_1$이 자기보다 느린 $H_2$를 따라잡으면 $H_1$은 속도를 $H_2$에 맞춰 늦춘다.

애니의 말에는 최고 속도가 없어서 애니가 정하는 어떤 속도로도 달릴 수 있다. 단, 다른 말을 추월해서는 안 된다. 애니는 말과 함께 편안하게 가려고 출발 지점부터 목적지까지 전 구간을 하나의 일정한 순항 속도로 달리되, 그 속도로도 다른 말을 추월하지 않기를 바란다. 애니가 고를 수 있는 최대 속도를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $D$와 $N$이 주어진다. $D$는 모든 말의 목적지 위치(킬로미터)이고, $N$은 도로에 있는 다른 말의 수다. 이어지는 $N$개의 줄 중 $i$번째 줄에는 두 정수 $K_i$와 $S_i$가 주어진다. 각각 $i$번째 말의 처음 위치(킬로미터)와 최고 속도(시속 킬로미터)다.

제한

• $1 \le T \le 100$
• 모든 $i$에 대해 $0 < K_i < D \le 10^9$
• $i \ne j$이면 $K_i \ne K_j$ (같은 위치에서 출발하는 말은 없다)
• $1 \le S_i \le 10000$
• $1 \le N \le 2$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 애니가 다른 말을 추월하지 않고 쓸 수 있는 최대 순항 속도(시속 킬로미터)다. $y$는 소수점 아래 일곱째 자리에서 반올림해 소수점 아래 정확히 여섯 자리로 출력한다.

예제 입력의 1번 케이스에는 다른 말이 한 마리뿐이고 아주 느리다. 그 말은 25시간 뒤에 애니의 목적지에 닿는다. 시속 101킬로미터보다 빠르면 애니는 목적지에 닿기 전에 그 말을 추월하게 된다.

2번 케이스에는 말이 두 마리 있다. 빠른 말은 2시간 뒤 240킬로미터 지점에서 느린 말을 따라잡는다. 그 뒤 두 말은 느린 말의 속도로 1시간을 더 달려 300킬로미터 지점의 목적지에 닿는다. 애니가 추월 없이 고를 수 있는 최대 속도는 시속 100킬로미터다.