Farmer John's Water Supply

Farmer John is facing a water shortage on his farm. He has n fields, and he wants to supply water to all of them. To do this, he can either dig a well in a field or connect two fields by constructing a water channel.

Digging a well in field \(i\) costs \(W_i\) dollars. Building a channel between field \(i\) and field \(j\) costs \(P_{i,j}\) dollars (and note that \(P_{i,j} = P_{j,i}\)).

The goal is to supply water to every field. A field is considered supplied if it either has its own well or is connected (directly or indirectly) to a field that has a well.

Please determine the minimum total cost required to supply water to all fields.

Hint: You can model the problem by adding an extra "virtual" node that is connected to each field \(i\) with an edge weight of \(W_i\). The problem then reduces to finding a Minimum Spanning Tree (MST) of the resulting graph.

inputFormat

The first line contains a single integer \(n\) (the number of fields).

The second line contains \(n\) space-separated integers \(W_1, W_2, \dots, W_n\), where \(W_i\) is the cost to dig a well in field \(i\).

The following \(n\) lines each contain \(n\) space-separated integers. The \(j\)-th integer in the \(i\)-th line is \(P_{i,j}\), representing the cost to build a channel between field \(i\) and field \(j\) (with \(P_{i,j} = P_{j,i}\)).

outputFormat

Output a single integer, the minimum total cost to supply water to all the fields.

sample

3
1 2 2
0 1 1
1 0 1
1 1 0

3