포니 익스프레스

때는 1860년이며, 포니 익스프레스는 미국 동해안과 서해안을 잇는 가장 빠른 우편 배달 시스템이다. 이 시스템은 서로 다른 N개의 도시에 서비스를 제공한다. 각 도시에는 말이 한 마리씩 있으며("말 한 마리뿐인 마을"이라는 표현에서처럼), 각 말은 일정한 속도로 달리고 너무 지쳐 더 달릴 수 없게 되기 전까지 이동할 수 있는 최대 총거리가 정해져 있다.

포니 익스프레스 기수는 출발 도시의 말을 타고 출발한다. 기수는 도시에 도착할 때마다 현재 말을 계속 타거나 그 도시의 말로 갈아탈 수 있으며, 말을 갈아타는 데에는 시간이 들지 않는다. 말은 쉴 기회를 전혀 얻지 못하므로, 말이 이동할 수 있는 최대 총거리의 일부가 한 번 "소모되면" 영원히 소모된 상태로 남는다! 기수가 목적지 도시에 도착하면 우편물이 배달된다.

도시 사이의 경로는 회사 소유주, 입법자, 노동조합 대표, 그리고 사촌 Pete 사이의 복잡한 협상을 통해 정해졌다. 따라서 도시 사이의 거리는 반드시 상식에 부합하지는 않는다. 예를 들어 삼각 부등식을 반드시 만족하지는 않으며, 도시 A에서 도시 B까지의 거리는 도시 B에서 도시 A까지의 거리와 다를 수도 있다!

당신은 시간 여행을 하는 사업가이며, 미래에서 빠른 컴퓨터를 가져왔다. 컴퓨터 한 대만으로는 이메일 서비스를 구축하여 포니 익스프레스를 쓸모없게 만들 수 없지만, 이를 사용해 포니 익스프레스의 최적 경로 계획을 세울 수는 있다. 도시 사이의 경로와 각 도시의 말에 관한 모든 데이터, 그리고 출발 도시와 도착 도시의 쌍 목록이 주어질 때, 각 배달에 필요한 최소 시간을 빠르게 계산할 수 있는가? (이 모든 배달은 서로 독립적인 것으로 취급해야 한다. 한 경로에서 도시나 말을 사용하더라도 다른 경로에서 사용할 수 없게 되지는 않는다.)

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 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}$. (조사할 도시의 순서쌍은 한 테스트 케이스 안에서 반복되지 않는다.)

작은 데이터 세트 (테스트 세트 1 - 공개)

i + 1 ≠ j인 모든 i, j에 대해, $D_{ij}$ = -1. (도시들은 하나의 직선 위에 있으며, 각 경로는 그 직선에서 한 도시로부터 다음 도시로 이어진다.) Q = 1. $U_{1}$ = 1. $V_{1}$ = N. (계산할 배달은 직선 위의 첫 도시와 마지막 도시 사이의 배달뿐이다.)

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ Q ≤ 100. 모든 k에 대해, 1 ≤ $U_{k}$ ≤ N. 모든 k에 대해, 1 ≤ $V_{k}$ ≤ N.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

• 두 정수 N과 Q가 한 줄에 주어진다. N은 말이 있는 도시의 수이고, Q는 관심 있는 정류 지점 쌍의 수이다. 도시에는 1부터 N까지 번호가 매겨져 있다.

• N개의 줄이 주어지며, 각 줄에는 두 정수 $E_{i}$가 주어진다. 이는 i번째 도시의 말이 이동할 수 있는 최대 총거리(킬로미터)이고, $S_{i}$는 그 말이 달리는 일정한 속도(킬로미터/시간)이다.

• N개의 줄이 주어지며, 각 줄에는 N개의 정수가 주어진다. 이 줄들 중 i번째 줄의 j번째 정수 $D_{ij}$는 i번째 도시에서 j번째 도시로 가는 직접 경로가 없으면 -1이고, 그렇지 않으면 그 경로의 길이(킬로미터)이다.

• Q개의 줄이 주어지며, 각 줄에는 두 정수 $U_{k}$와 $V_{k}$가 주어진다. 이들은 각각 조사하려는 k번째 도시 쌍의 출발 지점과 목적지이다.

각 테스트 케이스마다 Case #x: y_{1} y_{2} ... y_{Q}을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, y_{k}는 도시 $U_{k}$에서 도시 $V_{k}$까지 편지를 배달하는 데 걸리는 최소 시간(시간 단위)이다.

각 y_{k}는 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ을 참고하라.

마지막 예제 케이스는 작은 데이터 세트에 나타나지 않는다는 점에 유의하라.

케이스 #1에는 두 가지 선택지가 있다. 도시 1의 말을 여행 내내 타거나, 도시 2에서 말을 갈아탈 수 있다. 두 말 모두 지구력이 충분하므로 두 선택지 모두 가능하다. 도시 2의 말이 더 빠르므로 갈아타는 편이 더 좋으며, 총시간은 1/3 + 1/4이다.

케이스 #2에는 말을 갈아탈 수 있는 중간 도시가 두 곳 있다. 하지만 도시 2에서 말을 갈아타면 새 말은 엄청나게 빠르지만 지구력이 충분하지 않으므로 도시 3에서 다시 갈아타야 한다. 현재 말을 계속 타면 도시 3에서 말을 갈아탈 수도 있고 갈아타지 않을 수도 있다. 따라서 세 가지 선택지와 각각의 총시간은 다음과 같다.

• 도시 2과 3 모두에서 말을 갈아탄다 (1/10 + 1/1000 + 10/8 = 1.351).

• 도시 3에서만 말을 갈아탄다 (2/10 + 10/8 = 1.45).

• 말을 전혀 갈아타지 않는다 (12/10 = 1.2).

케이스 #3에서는 각 배달마다 많은 선택지가 있다. 첫 배달(도시 2에서 도시 4까지)의 최적 방법은 10/1000의 시간에 도시 1로 이동하여 말을 갈아탄 다음, 도시 1의 말을 타고 도시 2, 3, 4 순서로 이동하는 것이다. 여기에는 (10 + 10 + 10) / 60의 시간이 걸린다.

두 번째 배달(도시 3에서 도시 2까지)에서는 먼저 도시 4로 갈 수밖에 없으며, 여기에는 10/5의 시간이 걸린다. 비교적 빠른 현재 말은 다른 어느 곳에도 갈 만큼 지구력이 충분하지 않으므로 도시 4의 말을 타야 한다. 그 말을 타고 15의 시간에 도시 1로 직접 갈 수도 있지만, 그보다는 6의 시간에 도시 2로 간 다음 도시 2의 엄청나게 빠른 말을 타고 단 10/1000의 추가 시간으로 도시 1에 도착하는 편이 더 빠르다.

케이스 #3의 세 번째 배달(도시 3에서 도시 1까지)에서는 이전 배달의 처음 두 단계를 따르는 것이 최적이며, 총시간은 10/5 + 6 = 8이다.