This republic day Avinash heard about moon walk which by the way is a dance move but he interpreted in literal terms and thought of doing so.

There are $N$ tourist spot on moon (all are numbered from $1$ to $N$ ). Avinash is at $1$ tourist spot and wished to do a moon walk on all $N$ tourist spots. Time taken to travel from $i^{th}$ to $j^{th}$ spot is given as $d_{ij}$_.  (NOTE $d_{ij}$ = $d_{ji}$ may NOT hold)

Though there are Q restrictions that must be satisfied 

Tourist spot $u_{i}$ must be visited before $v_{i}$.

Find the minimum time required to visit all the tourist spot. Last tourist spot can be anyone of them.

NOTE : All the tourist spot must be visited only once.

$\textbf{Input}$

First line of input contains the number of tourist spot $N$, from subsequent line there will be N lines each containing $N$ values $d_{ij}$​​​​​​​. 

On the next line we have $Q$​​​​​​​, and subsequent $Q$​​​​​​​ lines will contain two values each having $u_i$ and $v_i$​​​​​​​.

$\textbf{Output}$

Minimum time required to visit all the tourist spots.

$\textbf{Constraints}$

${1 \leq N \leq 14}$

${0 \leq d_{ij} \leq 10^{7}}$

${d_{ii} = 0}$

${0 \leq Q \leq N*(N-1)/2}$

${1 \leq u_{i} , v_{i} \leq N}$

${u_{i} \neq v_{i}}$