Drilling Head Control Unit

Assignment

Deepest Drill Company, Ltd is producing a new set of drilling heads. The drilling head control unit has a special durable design. It consists of a ceramic base disk on which all electronics is mounted. There are N slots situated on the perimeter of the base disk. There are also N devices to be installed in the slots on the disk. No slot can contain more than one device, but it is the advantage of the design that any device can be installed in any slot.

The installed devices are subsequently connected into a single network which has a prescribed tree topology. All connections between the devices must be laid on one side of the disk and cannot cross each other. Aside from that, the shapes and the lengths of the connections may be arbitrary.

The cost of installing a device in a slot depends on the particular slot and the particular device. There is a cost matrix C which element C(i, j) specifies the cost of installing the j-th device in the i-th slot. The total installation cost is the sum of costs of installing all devices on the base disk. It is desirable to assign the devices to the slots in such way that the total installation cost is minimized.

Image 1. An illustration of Example 1 below. a) The empty disk with 9 slots labeled 0, 1, …, 8. b) The prescribed topology of the connections between the given 9 devices which are labeled 0, 1, … 8. c) The optimal layout of the devices on the disk. The cost of installing a particular device in a particular slot is written in the speech bubble at the slot. All costs are specified in the cost matrix C given in Example 1.

The task

You are given the installation cost matrix and the tree topology of the device connections. Find the minimum total installation cost.

Input

The first line of input contains one integer N describing the number of the devices and number of the slots on the base disk. The slots and the devices are labeled by integers 0,1, …, N−1. The slots are situated on the perimeter of the base disk in the order given by their labels.
The installation cost matrix C is specified on the next N lines. Each of these lines represents one row of the matrix. The matrix entries are separated by one or more spaces. Note that input lines may contain one or more leading spaces. The value C(i, j) is a positive integer and it represents the cost of installing the j-th device in the i-th slot.
Finally, the input contains N−1 lines which specify the connection topology. Each of these lines contains the labels of two connected devices separated by space. The order of connections and the order of devices on a line is arbitrary.
It holds 4 ≤ N ≤ 13, 1 ≤ C(i, j) ≤ 1000 for all 0 ≤ i, j < N.

Output

Ouput consists of one text line with one integer representing the minimum installation cost.

Examples

Example 1

Input

9
18 12 19 18 17 19 18 16 19
14 18 17 19 18 19 17 19 18
16 15 19 18 13 15 17 15 19
18 16 18 16 18 19 18 17 18
19 18 19 18 16 17 19 18 14
15 19 17 18 19 18 17 15 18
18 17 15 16 19 12 19 17 17
19 15 18 19 17 18 16 19 14
18 17 13 18 17 17 18 17 18
0 2
1 2
2 3
3 4
2 7
5 6
6 7
7 8

Output

Image 2. The device installation resulting in minimum total installation cost in Example 1.

Example 2

Input

4
70 90 10 80
20 70 80 90
80 30 90 70
90 80 70 40
0 2
0 3
1 2

Output

Image 3. The device installation resulting in minimum total installation cost in Example 2.

Example 3

Input

6
 37 40 31 31 32 38
 22 21 39 10 20 30
 30 27 30 10 37 16
 22 19 36 10 17 21
 20 12 27 24 38 23
 26 11 38 28 10 10
0 1
0 2
0 3
3 4
3 5

Output

Image 4. The device installation resulting in minimum total installation cost in Example 3.

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.

Link to public data set