Minimizing Magical Artifacts Backlash

In the magical realm, Cozy Glow has secretly assembled a magical array composed of several enchanted artifacts. Each artifact possesses a mana value \(M_i\) and every pair of distinct artifacts shares an association value \(A_{ij}\) (with \(A_{ij} = A_{ji}\) and \(A_{ii} = 0\)).

When an artifact is removed from the array, it inflicts a backlash equal to its mana value multiplied by the sum of the association values between that artifact and every artifact that remains. Formally, if artifact \(i\) is removed while artifact \(j\) is still present, the backlash incurred is:

\[ M_i \times A_{ij} \]

Thus, for any pair of artifacts \(i\) and \(j\), one of them will be removed first and will contribute \(\min(M_i, M_j) \times A_{ij}\) to the total backlash. The total backlash over all pairs in an optimal removal order is:

\[ \sum_{1 \leq i < j \leq n} A_{ij} \cdot \min(M_i, M_j) \]

Your task is to compute this minimal total backlash.

inputFormat

The input begins with a single integer \(n\) indicating the number of artifacts.

The next line contains \(n\) space-separated integers representing the mana values \(M_1, M_2, \dots, M_n\) of the artifacts.

Then follow \(n\) lines, each containing \(n\) space-separated integers. The \(j\)-th number in the \(i\)-th line represents the association value \(A_{ij}\) between artifact \(i\) and artifact \(j\). It is guaranteed that \(A_{ij} = A_{ji}\) for all \(i \neq j\) and \(A_{ii} = 0\).

outputFormat

Output a single integer representing the minimum total backlash.

sample

2
3 5
0 2
2 0

6