Pony Express (Small)

It is the year 1860, and the Pony Express is the fastest mail delivery system joining the East and West coasts of the United States. The system covers $N$ different cities. Each city has exactly one horse. Every horse travels at its own constant speed and has a maximum total distance it can cover before it is too tired to continue.

The rider starts out on the starting city's horse. Every time the rider reaches a city, the rider may keep the current horse or switch to that city's horse. Switching takes no time. Horses never get a chance to rest, so once part of a horse's maximum total distance is used up, it is used up forever. The mail is delivered when the rider reaches the destination city.

The routes between cities were settled by complicated negotiations between the company owners, lawmakers, union delegates, and cousin Pete. That is why the distances between cities do not follow common sense. They do not have to satisfy the triangle inequality, and the distance from city A to city B may differ from the distance from city B to city A.

You are a time traveling entrepreneur and you brought a fast computer back from the future. One computer is not enough to start an e-mail service and put the Pony Express out of business, but you can use it to plan optimal routes for the Pony Express. You are given all data about the routes between cities and the horses in each city, together with a list of pairs of starting and ending cities. Compute the minimum time needed for each delivery. The deliveries are independent. Using a city or a horse on one route does not make it unavailable on another route.

The first line contains the number of test cases, $T$. $T$ test cases follow. Each test case has this form.

• One line with two integers $N$ and $Q$. $N$ is the number of cities with horses and $Q$ is the number of pairs of stops to investigate. Cities are numbered from $1$ to $N$.
• $N$ lines, each with two integers $E_i$ and $S_i$. $E_i$ is the maximum total distance in kilometers that the horse in city $i$ can go, and $S_i$ is the constant speed in kilometers per hour at which that horse travels.
• $N$ lines, each with $N$ integers. The $j$-th integer on the $i$-th of these lines, $D_{ij}$, is $-1$ if there is no direct route from city $i$ to city $j$, and the length of that route in kilometers otherwise.
• $Q$ lines, each with two integers $U_k$ and $V_k$, the starting city and the destination city of the $k$-th pair to investigate.

Limits.

• $1 ≤ T ≤ 100$
• $2 ≤ N ≤ 100$
• $1 ≤ E_i ≤ 10^9$ for all $i$
• $1 ≤ S_i ≤ 1000$ for all $i$
• $-1 ≤ D_{ij} ≤ 10^9$ for all $i$, $j$
• $D_{ii} = -1$ for all $i$. There is no direct route from a city to itself.
• $D_{ij} ≠ 0$ for all $i$, $j$
• $U_k ≠ V_k$ for all $k$
• The delivery from city $U_k$ to city $V_k$ can be completed with the given horses, for all $k$.
• $U_l ≠ U_m$ or $V_l ≠ V_m$ for all different $l$, $m$. No ordered pair of cities to investigate repeats within a test case.
• $D_{ij} = -1$ for all $i$, $j$ with $i + 1 ≠ j$. The cities stand in a single line, and every route goes from one city to the next city in the line.
• $Q = 1$
• $U_1 = 1$
• $V_1 = N$. The only delivery to compute runs from the first city in the line to the last one.

For each test case, output one line containing Case #x: y1 y2 ... yQ, where $x$ is the test case number starting from $1$ and $y_k$ is the minimum time, in hours, to deliver a letter from city $U_k$ to city $V_k$.

Print each $y_k$ rounded to six digits after the decimal point, always with all six digits. No input is given for which that rounding is ambiguous at the sixth digit.

In the first test case of the example there are two options: use the horse in city 1 for the whole trip, or change horses in city 2. Both horses have enough endurance, so both options work. The horse in city 2 is faster, so changing is better, for a total time of $1/3 + 1/4$.

In the second test case of the example there are two intermediate cities where you can change horses. If you change horses in city 2, the new horse is blazingly fast but does not have enough endurance, so you are forced to change again in city 3. If you keep your horse, you can decide in city 3 whether to change. The three options and their total times are:

1. Change horses in both city 2 and city 3. $1/10 + 1/1000 + 10/8 = 1.351$
2. Change horses just in city 3. $2/10 + 10/8 = 1.45$
3. Never change horses. $12/10 = 1.2$