포니 익스프레스 (스몰)

1860년, 포니 익스프레스는 미국 동부 해안과 서부 해안을 잇는 가장 빠른 우편 배달 체계다. 이 체계는 서로 다른 도시 $N$개를 지난다. 각 도시에는 말이 한 마리씩 있다. 말마다 달리는 속도가 일정하게 정해져 있고, 지쳐서 더 달릴 수 없게 되기까지 갈 수 있는 최대 총 거리도 정해져 있다.

배달원은 출발 도시의 말을 타고 떠난다. 어느 도시에 닿든 타고 온 말을 그대로 타거나 그 도시의 말로 갈아탈 수 있고, 갈아타는 데 드는 시간은 없다. 말은 쉴 기회가 없으므로 한 번 쓴 거리는 영영 되돌아오지 않는다. 배달원이 도착 도시에 닿으면 우편이 배달된다.

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

당신은 시간 여행을 하는 사업가이고, 미래에서 빠른 컴퓨터를 한 대 가져왔다. 컴퓨터 한 대로 전자우편 서비스를 차려 포니 익스프레스를 밀어낼 수는 없지만, 포니 익스프레스의 최적 경로를 짜는 데는 쓸 수 있다. 도시 사이의 노선과 각 도시의 말에 대한 자료, 그리고 출발 도시와 도착 도시 쌍의 목록이 주어진다. 각 배달에 필요한 최소 시간을 구하라. 배달은 서로 독립이다. 어떤 배달에서 도시나 말을 썼다고 해서 다른 배달에서 그 도시나 말을 못 쓰게 되지는 않는다.

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

• 첫 줄에 정수 $N$과 $Q$가 주어진다. $N$은 말이 있는 도시의 수이고, $Q$는 확인할 도시 쌍의 수다. 도시에는 $1$번부터 $N$번까지 번호가 붙어 있다.
• 다음 $N$개의 줄에는 각각 정수 $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 ≤ T ≤ 100$
• $2 ≤ N ≤ 100$
• 모든 $i$에 대해 $1 ≤ E_i ≤ 10^9$
• 모든 $i$에 대해 $1 ≤ S_i ≤ 1000$
• 모든 $i$, $j$에 대해 $-1 ≤ D_{ij} ≤ 10^9$
• 모든 $i$에 대해 $D_{ii} = -1$이다. 자기 자신으로 가는 직통 노선은 없다.
• 모든 $i$, $j$에 대해 $D_{ij} ≠ 0$
• 모든 $k$에 대해 $U_k ≠ V_k$
• 모든 $k$에 대해 $U_k$번 도시에서 $V_k$번 도시로 가는 배달을 주어진 말로 마칠 수 있음이 보장된다.
• 서로 다른 $l$, $m$에 대해 $U_l ≠ U_m$이거나 $V_l ≠ V_m$이다. 한 테스트 케이스 안에서 같은 순서쌍이 두 번 나오지 않는다.
• $i + 1 ≠ j$인 모든 $i$, $j$에 대해 $D_{ij} = -1$이다. 도시가 한 줄로 늘어서 있고, 모든 노선은 한 도시에서 줄의 바로 다음 도시로 간다.
• $Q = 1$
• $U_1 = 1$
• $V_1 = N$이다. 계산할 배달은 줄의 첫 도시에서 마지막 도시로 가는 하나뿐이다.

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

각 $y_k$는 소수점 아래 여섯째 자리까지 반올림해서, 소수점 아래 여섯 자리를 모두 채워 출력한다. 여섯째 자리 반올림 결과가 갈리는 입력은 주어지지 않는다.

예제의 첫 번째 테스트 케이스에는 선택지가 둘 있다. 1번 도시의 말로 끝까지 가거나, 2번 도시에서 갈아타는 것이다. 두 말 모두 지구력이 넉넉하므로 둘 다 가능하다. 2번 도시의 말이 더 빠르니 갈아타는 쪽이 낫고, 걸리는 시간은 $1/3 + 1/4$이다.

예제의 두 번째 테스트 케이스에는 갈아탈 수 있는 중간 도시가 둘 있다. 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$