There are $N$  islands. There can be a maximum of two bridges(both bidirectional) connecting a pair of islands. Every bridge has a maintenance cost. You have to reduce the cost of maintenance as much as possible by breaking some of these bridges because a broken bridge does not need any maintenance. The bridges should be broken in such a way that any pair of islands should be reachable from each other. What is the maximum cost which can be reduced?

You are given the maintenance cost of each bridge in the form of $2D$ array. $Arr$. $Arr[i][j]$ is the maintenance cost of one of the bridges between $i^{th}$ and $j^{th}$ islands.

Note

• $Arr[i][i] = 0$ for $1 <= i <= N$
• $Arr[i][j]$ and $Arr[j][i]$ are the maintenance cost of different bridges for $i != j$
• If $Arr[i][j] = 0$, then it is not a bridge

Input format

• First line: $N$ denoting the total number of islands
• ​​​​​​$N$ lines follow:
  •  $i^{th}$ line: $N$ space-separated integers denoting the $i^{th}$ row of Arr

Output format

• Print the answer to the problem.

Constraints
$1 \le N \le 10^3$
$1 \le$ Maintenance cost of each bridge $\le 10^3$