Ambrosian Roads

Ambrosian

All roads in a country called Ambrosia have been destroyed by floods. The current mission is to restore communication between its cities. Every city has a construction department which can deals with the roads that are connected to that city. The construction department of any city can construct only one road and can manage only one constructed road.

Ambrosia has cities numbered from 1 to N. We need to build roads in such a way that Ambosia becomes fully connected. This means that there will be at least one path between any pair of cities in the country.

The Construction department of each city provided two lists for all roads that are connected to it. One list clearly states the money needed to construct the roads and another list which states the money required manage that road.

Your task is to find the minimum amount of money senate will spend on the construction and managing of roads with given constraint.

Note : Managing is possible only for the road that has been constructed.

Input Format
First line of input contains N, which is the number of cities in Ambrosia.
Next N line contains N integers. and the Jth integer in Ith line describe the amount of money Ith city will take for construction of roads between city I and J. Next N line contains N integers. The Jth integer in the Ith line describe the amount of money Ith city will take for managing of roads between city I and J.

Output format
Single line contains the minimum amount of money senate will spend on the construction and management of roads with given constraint (as a recap, the constraint is that the construction department of any city can construct only one road and can manage only one constructed road).

Constraints
1 <= N <= 30
1 <= maximum money for construction and managing of roads <= 100

Sample Input

2
72 53
52 8
31 56
11 16
Sample Output

63