Description

有$N$ 个村庄，编号为$1～N$ ，需要建造一 些道路，使每两个村庄之间都可以相互连接。两个村庄$A$和$B$是相连的， 当且仅当$A$和$B$之间有一条道路，或者存在一个村庄$C$，$A$和$C$相连且$C$和$B$ 相连。已知一些村庄之间已经有一些道路，你的工作是修建一些道路， 使所有村庄都连通起来，所有道路的长度之和最小。

Format

Input

第$1$行是整数$N （3≤N ≤100）$，表示村庄的数量；然后 是$N$ 行，其中第$i$ 行包含$N$ 个整数，第$j$ 个整数表示村庄$i$ 和村庄$j$ 之 间的距离（距离为$[1,1000]$内的整数）；接着是整数$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

来源

POJ2421