该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

有N个村庄，编号从1到N，我们知道一些村庄之间已经有了一些道路，你的任务是修建一些格外的道路，使任意两个村庄可以相互到达，并使新修道路的长度总和最小。

Input

第一行是整数N (3 <= N <= 100)，表示村庄的数量。然接下来是N行N列的矩阵，第i行j列表示村庄i与村庄j的距离。

然后是整数Q (0 <= Q <= N * (N + 1) / 2)，接下来Q行，每行两个整数a和b(1 <= a < b <= N)，这意味着村庄a和村庄b之间的道路已经建成。

Output

你应该输出一行包含一个整数，这是需要新修建的道路的长度总和，这样所有的村庄都连接起来，你要使这个值最小。

Samples

3
0 990 692
990 0 179
692 179 0
1
1 2

179