Spies

You are M, the head of an intelligence agency that employs $N$ spies, code-named $1$ through $N$. Each spy has been assigned to a different country and has obtained one important piece of information there.

Your task has two stages:

1. Arrange meetings between spies. In each meeting exactly two spies meet and exchange all the information they currently hold, whether obtained themselves or learned in earlier meetings. Because arranging a secret meeting between two spies in different countries is difficult, every possible meeting has a fixed price.
2. After all meetings are over, choose a subset of the spies and send them together on the assignment. Sending spy $k$ costs $M_k$. The assignment succeeds only if the chosen spies together know every piece of information originally obtained by the spies who are NOT sent.

Find the minimum possible total price of preparing and carrying out the assignment: the sum of the prices of the meetings you arrange plus the sending costs of the chosen spies.

The first line contains an integer $N$, the number of spies ($2 \le N \le 1000$).

Each of the next $N$ lines contains $N$ integers. The integer in row $k$, column $m$ is the price of a meeting between spies $k$ and $m$; it equals the integer in row $m$, column $k$, and the diagonal entries ($k = m$) are $0$. Every meeting price is a positive integer of at most $10^6$.

The last line contains $N$ integers $M_1, M_2, \ldots, M_N$ ($1 \le M_k \le 10^6$), where $M_k$ is the cost of sending spy $k$ on the assignment.

Print a single integer: the minimum total price.

In the first sample, arrange meetings between spies 1 and 2 and between spies 2 and 3, then send spy 2.

In the second sample, arrange a meeting between spies 2 and 3, then send spies 1 and 2.

In the third sample, arrange meetings between spies 2 and 4, then 1 and 2, then 3 and 5, and send spies 1 and 3 (sending 1 and 5 works as well).