Watering Fields

A farmer wants to supply water to all N fields. There are two ways to do this. A well can be dug directly in a field, or water can be brought from another field that already has water by connecting the two fields.

You are given the cost of digging a well in each field and the cost of connecting each pair of fields. Find the minimum total cost needed to supply water to every field.

The first line contains the number of fields N.

The next N lines contain the costs Wi in order, where Wi is the cost of digging a well in field i.

The following N lines each contain N integers. The j-th integer on the i-th of these lines, Pi,j, is the cost of connecting field i and field j with a waterway.

The conditions are as follows.

• 1 ≤ N ≤ 300
• 1 ≤ Wi ≤ 100,000
• 1 ≤ Pi,j ≤ 100,000 (i ≠ j)
• Pi,j = Pj,i
• Pi,i = 0

Print the minimum cost required to supply water to every field.