E. Generation and transmission network
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We wish to construct an electricity generation and transmission network in a cluster of $$$N$$$ islands. To this end, we have calculated a cost $$$p(x)$$$ to (potentially) build a generating station on each island $$$x$$$, as well as a cost $$$c(x,y)$$$ to build an energy transmission line between any two islands $$$x$$$ and $$$y$$$. An island is connected to the grid if it has a generating station built on it, or if there is a sequence of power transmission lines connecting it to an island that has a generating station. Our goal is to connect all $$$N$$$ islands to the grid, minimizing the total network construction cost.

Input

The first line of the input contains an integer $$$N$$$ which gives the number of islands in the cluster.

The next $$$N$$$ lines of the input are sequences of $$$N$$$ numbers that form an $$$N$$$-by-$$$N$$$ array $$$A$$$, such that each diagonal entry $$$A[x,x]$$$ corresponds to the cost $$$p(x)$$$ to build generating station on island $$$x$$$ (that is, $$$'A[x,x] = p(x)'$$$), while each non-diagonal entry $$$A[x,y]$$$ corresponds to the cost $$$c(x,y)$$$ to build an energy transmission line between two islands $$$x$$$ and $$$y$$$ (that is, $$$'A[x,y] = c(x,y)'$$$).

Output

A single integer that gives the total construction cost of the network.

Example
Input
4
10 8 10 14
8 15 9 13
10 9 12 12
14 13 12 11
Output
38
Note

Limits

- $$$1 \leq N \leq 1000$$$

- $$$1 \leq A[x,y] \leq 10000, \forall 1 \leq x,y \leq N$$$