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

数据有误，待修复！

有 $N$ 个村庄，编号从 $1$ 到 $N$ ，你需要修建一些道路，使得每两个村庄都可以相互连接。我们说两个村庄 $A$ 和 $B$ 是连接的，当且仅当 $A$ 和 $B$ 之间有一条道路，或者存在一个村庄 $C$ ，使得 $A$ 和 $C$ 之间有一条道路，且 $C$ 和 $B$ 是连接的。 我们知道已经有一些村庄之间已经存在一些道路，你的任务是修建一些道路，使得所有村庄都连接起来，并且所修建的所有道路的长度之和最小。

输入格式

第一行是一个整数 $N$ ($3$ $\leq$ $N$ $\leq$ $100$) ，表示村庄的数量。接下来是 $N$ 行，第 $i$ 行包含 $N$ 个整数，其中第 $j$ 个整数表示村庄 $i$ 和村庄 $j$ 之间的距离（距离应为一个在 $[1, 1000]$ 范围内的整数）。 然后是一个整数 $Q$ ($0$ $\leq$ $Q$ $\leq$ $N * (N + 1) /2$) 。接下来是 $Q$ 行，每行包含两个整数 $a$ 和 $b$ $(1 <= a < b <= N)$，表示村庄 $a$ 和村庄 $b$ 之间已经修建了一条道路。

输出格式

你应该输出一行，包含一个整数，表示修建所有道路使得所有村庄连接起来的最小总长度。

输入样例

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

输出样例

179

提示

无