Steed 2: Cruise Control (Small)

Annie is a bus driver with a high stress job. She tried to unwind on a Caribbean cruise, but that turned out to be stressful too, so she recently took up horseback riding.

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 markers increase 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. The $i$-th of these horses starts at kilometer $K_i$ and travels at its maximum speed of $S_i$ kilometers per hour.

Horses are very polite, so 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 you may treat every horse as a single point. Every horse other than Annie's travels at its maximum speed, except that when $H_1$ catches up to a slower horse $H_2$, $H_1$ slows down to match the speed of $H_2$.

Annie's horse has no maximum speed and can travel at any speed Annie chooses, as long as it does not pass another horse. For a smooth ride, Annie wants to pick a single constant cruise control speed for the whole trip, from her current position to the destination, so that her horse never passes another horse. Find the maximum such speed.

The first line contains the number of test cases, $T$. $T$ test cases follow. Each test case begins with two integers $D$ and $N$: the destination position of every horse in kilometers, and the number of other horses on the road. Then $N$ lines follow. The $i$-th of those lines holds 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 every $i$
• $K_i \ne K_j$ for every $i \ne j$, so no two horses start at the same position
• $1 \le S_i \le 10000$
• $1 \le N \le 2$

For each test case, print one line in the form Case #x: y, where x is the test case number starting from 1 and y is the maximum constant speed in kilometers per hour that Annie can use without passing another horse. Print y with exactly six digits after the decimal point, rounding half up at the seventh digit.

In case 1 of the sample input there is one other horse and it is very slow: it reaches Annie's destination after 25 hours. Any speed above 101 kilometers per hour would make Annie pass that horse before she reaches the destination.

In case 2 there are two other horses. The faster horse catches the slower one at kilometer 240 after 2 hours. The two horses then travel at the slower horse's speed for 1 more hour and reach the destination at kilometer 300. The maximum speed Annie can pick without passing a horse is 100 kilometers per hour.