You are M, the head of the intelligence agency which employs $N$ spies with codenames from $1$ to $N$. Each of the spies has been assigned a different country and obtained an important piece of information there. Your task is the following:

1. Organize meetings between some of the spies. In each meeting, exactly two spies meet and exchange all information that they have obtained themselves or learned from other spies in previous meetings. Organizing a top-secret meeting between two spies in different countries is difficult, so each potential meeting has a price.
2. After all the meetings have concluded, select a subset of spies and send them together on the world-saving (and woman-romancing) assignment. Sending a spy $k$ on the assignment costs $M_k$. For the assignment to succeed, it is important that the spies together know all the information obtained by the remaining spies.

Find the minimum total price of preparing and executing this assignment.

Input Specification

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

Each of the following $N$ lines contains $N$ positive integers not exceeding ${10}^6$. The number in row $k$ and column $m$ represents the price of a meeting between spies $k$ and $m$ and, of course, equals the number in row $m$ and column $k$ (for $k=m$ the number will be $0$).

The following line contains $N$ positive integers $M_k$ $(1\le M_k\le {10}^6)$, the prices of sending each spy on the assignment, in order for spies $1,2,\dots ,N$.

Output Specification

The first and only line of output must contain the required minimum total price.

Scoring

In test data with $N\le 30$, which is worth a total of $40$ points, it will be optimal to send at most four spies on the assignment.

In test data worth a total of $50$ points, all prices of sending spies on assignment are equal.

Sample Input 1

3
0 6 9
6 0 4
9 4 0
7 7 7

Sample Output 1

17

Explanation for Sample Output 1

We will organize meetings between spies $1$ and $2$, then $2$ and $3$, and send spy $2$ on the assignment.

Sample Input 2

3
0 17 20
17 0 10
20 10 0
15 9 12

Sample Output 2

34

Explanation for Sample Output 2

We will organize a meeting between spies $2$ and $3$, and send spies $1$ and $2$ on the assignment.

Sample Input 3

5
0 3 12 15 11
3 0 14 3 20
12 14 0 11 7
15 3 11 0 15
11 20 7 15 0
5 10 10 10 10

Sample Output 3

28

Explanation for Sample Output 3

We will organize meetings between spies $2$ and $4$, then $1$ and $2$, then $3$ and $5$, and send spies $1$ and $3$ (or $1$ and $5$) on the assignment.