说明

有$N$个村庄,编号从1到$N$,请你建立一些道路,使得任意两个村庄可以相连。我们说两个村$A$和$B$是相连的,当且仅当有一条公路在$A$与$B$之间,或存在一个村庄$C$,有一条的道路连接着$A$和$C$之间,一条连接着$B$和$C$。

我们知道,已经有一些道路在一些村庄之间,你的工作是再建一些道路,使得所有的村庄连接并且所有的道路建造总和最低。

输入格式

第一行是一个整数$N(3 \leqslant N \leqslant 100)$,表示村庄的数量。接下来$N$行,每行包含$N$个整数,在这$N$行中的第$i$行的第$j$个整数$A_{ij}$表示村庄$i$到村庄$j$建立道路的费用 ($1 \leqslant Aij \leqslant 1000$)。

然后有一个整数$Q(0 \leqslant Q \leqslant N *(N + 1)/2)$。接下来再$Q$行,每一行包含两个整数$a$和$b(1 \leqslant a < b \leqslant N)$,即村庄$a$和$b$之间已经建成道路。

输出格式

你应该输出一行包含一个整数,表示所有村庄都连接所要建设道路的最小费用。

样例

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

179