Pony Express (Large)

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. This system serves $N$ different cities. Each city has one horse. Every horse travels at a certain constant speed and has a maximum total distance it can travel before it becomes too tired to continue.

The Pony Express rider starts off 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 is instantaneous. Horses never get a chance to rest, so whenever part of a horse's maximum total distance is used up, it is used up forever. When the rider reaches the destination city, the mail is delivered.

The routes between cities were established through complicated negotiations between company owners, lawmakers, union delegates, and cousin Pete. That means the distances between cities do not necessarily follow common sense. They do not necessarily comply with the triangle inequality, and the distance from city A to city B might be different from the distance from city B to city A.

You are a time traveling entrepreneur, and you have brought a fast computer from the future. A single computer is not enough for you to set up an e-mail service and make the Pony Express obsolete, but you can use it to make optimal routing plans for the Pony Express. Given all data about routes between cities and the horses in each city, and a list of pairs of starting and ending cities, compute the minimum time necessary for each delivery. Treat all deliveries as independent: using cities or horses on one route does not make them unavailable on other routes.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case is described as follows.

• 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 we are interested in. Cities are numbered from 1 to $N$.
• $N$ lines, the $i$-th of which contains two integers $E_i$ and $S_i$. $E_i$ is the maximum total distance, in kilometers, the horse in the $i$-th city can go, and $S_i$ is the constant speed, in kilometers per hour, at which that horse travels.
• $N$ lines, each containing $N$ integers. The $j$-th integer on the $i$-th of these lines, $D_{ij}$, is $-1$ if there is no direct route from the $i$-th city to the $j$-th city, and the length of that route in kilometers otherwise.
• $Q$ lines, each containing two integers $U_k$ and $V_k$, the starting and destination city of the $k$-th pair of cities to investigate.

Limits:

• $1 \le T \le 100$
• $2 \le N \le 100$
• $1 \le Q \le 100$
• $1 \le E_i \le 10^9$ for all $i$
• $1 \le S_i \le 1000$ for all $i$
• $-1 \le D_{ij} \le 10^9$ and $D_{ij} \ne 0$ for all $i$, $j$
• $D_{ii} = -1$ for all $i$ (there are no direct routes from a city to itself)
• $1 \le U_k \le N$, $1 \le V_k \le N$ and $U_k \ne V_k$ for all $k$
• For all different $l$ and $m$ in one test case, the ordered pairs $(U_l, V_l)$ and $(U_m, V_m)$ differ
• The delivery from $U_k$ to $V_k$ can always be accomplished with the given horses, for all $k$
• Every queried answer is smaller than $10^6$ hours, and the data is such that rounding it to six decimal places is unambiguous

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$.

Round each $y_k$ to six decimal places and print exactly six digits after the decimal point. Separate values with a single space.

Here is an explanation of each case in the example.

In Case #1 there are two options: use the horse in city 1 for the entire trip, or change horses in city 2. Both horses have enough endurance, so both options work. The horse in city 2 is faster, so it is better to change, for a total time of 1/3 + 1/4.

In Case #2 there are two intermediate cities where you can change horses. If you change horses in city 2, your new horse is very fast but does not have enough endurance, so you are forced to change again in city 3. If you keep your horse, you still have the option to change horses in city 3. 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).

In Case #3 there are many alternatives for each delivery. The optimal one for the first delivery (city 2 to city 4) is to go to city 1 in time 10/1000, change horses, and then go to cities 2, 3 and 4, in that order, using the horse from city 1, which takes time (10 + 10 + 10) / 60.

For the second delivery (city 3 to city 1) you have no choice but to first go to city 4, which takes time 10/5. Your fairly fast horse does not have enough endurance left to get anywhere else, so you need to grab the horse in city 4. You could use it to get directly to city 1 in time 15, but riding it to city 2 in time 6 and then using the very fast horse in city 2 to get to city 1 in just 10/1000 extra time is quicker.

In the third delivery (city 3 to city 2) it is optimal to use the first two steps of the previous one, for a total time of 10/5 + 6 = 8.