포니 익스프레스 (라지)

1860년, 포니 익스프레스는 미국 동부 해안과 서부 해안을 잇는 가장 빠른 우편 배달 수단이다. 이 조직은 $N$개의 도시를 연결한다. 도시마다 말이 한 마리씩 있고, 말은 저마다 정해진 속도로 달리며 지쳐서 더 달리지 못할 때까지 갈 수 있는 최대 주행 거리가 정해져 있다.

배달원은 출발 도시의 말을 타고 출발한다. 어떤 도시에 도착할 때마다 타고 있던 말을 계속 타거나 그 도시의 말로 갈아탈 수 있고, 갈아타는 데 드는 시간은 0이다. 말은 도중에 쉬지 못하므로 한 번 소모한 주행 거리는 영영 돌아오지 않는다. 배달원이 도착 도시에 닿으면 배달이 끝난다.

도시 사이의 경로는 회사 소유주, 입법자, 노조 대표, 그리고 사촌 피트가 벌인 복잡한 협상으로 정해졌다. 그래서 거리가 상식과 맞지 않는다. 삼각 부등식이 성립하지 않을 수 있고, 도시 A에서 도시 B까지의 거리가 도시 B에서 도시 A까지의 거리와 다를 수도 있다.

당신은 미래에서 빠른 컴퓨터를 가져온 시간 여행 사업가다. 컴퓨터 한 대로 전자우편 서비스를 차려 포니 익스프레스를 한물간 물건으로 만들기에는 모자라지만, 최적의 배달 계획을 짜는 데는 쓸 수 있다. 도시 사이의 경로와 각 도시의 말에 대한 자료, 그리고 출발 도시와 도착 도시 쌍의 목록이 주어질 때 각 배달에 필요한 최소 시간을 구하라. 배달은 서로 독립이다. 한 배달에서 어떤 도시나 말을 썼더라도 다른 배달에서는 그대로 다시 쓸 수 있다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지고, 각 테스트 케이스의 형식은 다음과 같다.

• 첫 줄에 두 정수 $N$과 $Q$가 주어진다. $N$은 말이 있는 도시의 수, $Q$는 조사하려는 도시 쌍의 수다. 도시는 1번부터 $N$번까지 번호가 매겨져 있다.
• 다음 $N$개 줄 중 $i$번째 줄에는 두 정수 $E_i$와 $S_i$가 주어진다. $E_i$는 $i$번 도시의 말이 갈 수 있는 최대 주행 거리(킬로미터), $S_i$는 그 말이 달리는 일정한 속도(시간당 킬로미터)다.
• 다음 $N$개 줄에는 각각 $N$개의 정수가 주어진다. 이 중 $i$번째 줄의 $j$번째 정수 $D_{ij}$는 $i$번 도시에서 $j$번 도시로 가는 직행 경로가 없으면 $-1$이고, 있으면 그 경로의 길이(킬로미터)다.
• 다음 $Q$개 줄에는 각각 두 정수 $U_k$와 $V_k$가 주어진다. 각각 $k$번째로 조사할 도시 쌍의 출발 도시와 도착 도시다.

제한:

• $1 \le T \le 100$
• $2 \le N \le 100$
• $1 \le Q \le 100$
• 모든 $i$에 대해 $1 \le E_i \le 10^9$
• 모든 $i$에 대해 $1 \le S_i \le 1000$
• 모든 $i$, $j$에 대해 $-1 \le D_{ij} \le 10^9$이고 $D_{ij} \ne 0$
• 모든 $i$에 대해 $D_{ii} = -1$ (자기 자신으로 가는 직행 경로는 없다)
• 모든 $k$에 대해 $1 \le U_k \le N$, $1 \le V_k \le N$, $U_k \ne V_k$
• 한 테스트 케이스 안에서 서로 다른 $l$, $m$에 대해 순서쌍 $(U_l, V_l)$과 $(U_m, V_m)$은 서로 다르다
• 모든 $k$에 대해 $U_k$에서 $V_k$로 가는 배달은 주어진 말로 반드시 완수할 수 있다
• 모든 질의의 정답은 $10^6$시간 미만이고, 소수점 여섯째 자리까지 반올림한 값이 유일하게 정해지도록 자료가 주어진다

각 테스트 케이스마다 Case #x: y1 y2 ... yQ 형식으로 한 줄씩 출력한다. $x$는 테스트 케이스 번호(1부터 시작)이고, $y_k$는 $U_k$번 도시에서 $V_k$번 도시로 편지를 배달하는 데 걸리는 최소 시간(시간 단위)이다.

각 $y_k$는 소수점 아래 여섯째 자리까지 반올림해서 소수점 아래 자리를 정확히 여섯 개 적는다. 값 사이는 공백 하나로 구분한다.

예제의 각 케이스를 설명한다.

Case #1에는 두 가지 방법이 있다. 1번 도시의 말로 끝까지 가거나, 2번 도시에서 갈아타는 것이다. 두 말 모두 주행 거리가 넉넉하므로 둘 다 가능하다. 2번 도시의 말이 더 빠르니 갈아타는 쪽이 낫고, 걸리는 시간은 1/3 + 1/4이다.

Case #2에는 갈아탈 수 있는 중간 도시가 둘이다. 2번 도시에서 갈아타면 새 말이 무척 빠르지만 남은 주행 거리가 모자라서 3번 도시에서 또 갈아타야 한다. 타던 말을 그대로 두면 3번 도시에서 갈아탈지 말지 고를 수 있다. 세 가지 방법과 각각의 시간은 다음과 같다.

1. 2번 도시와 3번 도시에서 모두 갈아탄다 (1/10 + 1/1000 + 10/8 = 1.351).
2. 3번 도시에서만 갈아탄다 (2/10 + 10/8 = 1.45).
3. 한 번도 갈아타지 않는다 (12/10 = 1.2).

Case #3은 배달마다 선택지가 많다. 첫 번째 배달(2번에서 4번)은 10/1000 시간을 들여 1번 도시로 가서 갈아탄 뒤, 1번 도시의 말로 2번, 3번, 4번 도시를 차례로 지나는 것이 최적이고 (10 + 10 + 10) / 60 시간이 걸린다.

두 번째 배달(3번에서 1번)은 먼저 10/5 시간을 들여 4번 도시로 가는 수밖에 없다. 타고 있던 말은 제법 빠르지만 남은 주행 거리가 모자라 다른 곳으로는 갈 수 없으므로 4번 도시의 말로 갈아탄다. 이 말로 1번 도시까지 곧장 가면 15시간이 걸리지만, 2번 도시까지 6시간에 간 다음 2번 도시의 아주 빠른 말로 10/1000 시간을 더 쓰는 편이 빠르다.

세 번째 배달(3번에서 2번)은 두 번째 배달의 앞 두 구간을 그대로 쓰는 것이 최적이고, 모두 10/5 + 6 = 8시간이 걸린다.