Horse Cruise Control

Annie drives a bus and the job wears her down. She booked a Caribbean cruise to unwind, that turned out to be stressful too, so lately she rides horses instead.

Today Annie rides east along a long, narrow one way road that runs from west to east. She is at kilometer 0 of the road and her destination is at kilometer $D$. Kilometer marks grow from west to east.

$N$ other horses travel east on the same road. All of them keep going forever, and all of them are currently between Annie's horse and her destination. Horse $i$ starts at kilometer $K_i$ and runs at its maximum speed of $S_i$ kilometers per hour.

Horses are very polite. A horse $H_1$ never passes a horse $H_2$ that started ahead of $H_1$. Two or more horses may share the same position for any amount of time, and each horse counts as a single point. Every horse other than Annie's runs at its maximum speed, except that once $H_1$ catches up to a slower horse $H_2$ ahead of it, $H_1$ drops to the speed of $H_2$.

Annie's horse has no maximum speed, so it runs at any speed Annie chooses as long as it passes no other horse. For a smooth ride Annie wants a single constant speed for the whole trip, from her current position to the destination, and that speed must never make her pass another horse. Find the largest such speed.

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains two integers $D$ and $N$. $D$ is the destination position of every horse in kilometers, and $N$ is the number of other horses on the road. Each of the next $N$ lines contains two integers $K_i$ and $S_i$: the starting position in kilometers and the maximum speed in kilometers per hour of the $i$-th of the other horses.

Limits

• $1 \le T \le 100$
• $0 < K_i < D \le 10^9$ for all $i$
• $K_i \ne K_j$ for all $i \ne j$ (no two horses start at the same position)
• $1 \le S_i \le 10000$
• $1 \le N \le 1000$

For each test case, print one line of the form Case #x: p/q, where x is the test case number starting from 1 and p/q is the largest constant speed in kilometers per hour that Annie can hold without passing another horse, written as a fraction in lowest terms.

The answer is always rational. Use integers $p$ and $q$ with $\gcd(p, q) = 1$ and $q \ge 1$. When the answer is an integer $n$, print the denominator anyway, as n/1.

The first test case of the example has one other horse, and it is very slow. It reaches Annie's destination after 25 hours. Anything faster than 101 kilometers per hour makes Annie pass that horse before she reaches the destination, so the answer is 101/1.

The second test case has two other horses. The faster one catches the slower one at kilometer 240 after 2 hours. Both then run at the slower horse's speed for 1 more hour and reach the destination at kilometer 300. The largest speed Annie can choose without passing another horse is 100 kilometers per hour, so the answer is 100/1.