당신은 1 에서 N 까지 번호가 부여된 스파이를 둔 국장이다. 스파이는 다른 나라에 보내져 중요한 정보를 수집한다.

당신의 임무는

1. 스파이 사이의 미팅을 계획을 만들어야 한다. 각 미팅에는 정확히 두 명의 스파이가 만나서 그들이 습득한 정보나 전의 미팅에서 안 것을 교환한다. 스파이 사이의 미팅의 중요도가 주어진다.
2. 미팅 계획을 만든 후 , 스파이 중에 몇 명을 뽑아 세상구호를 위한 모임에 보내야 한다. k 번 스파이를 모임에 보내기 위한 비용은 Mk 이다. 중요한 사항은 이 모임에 보내는 스파이는 스파이의 모든 정보를 알수 있어야 한다.

입력

• 첫 줄에는 스파이 수 N 이 주어진다.(2 ≤ N ≤ 1000).
• 다음 N 줄에는 각 스파이들이 만났을 때의 비용이 주어진다. 비용은 10^6 을 넘지 않는다.
• 마지막 줄은 각 스파이를 모임에 보낼때의 비용 Mk(1 ≤ Mk ≤ 10^6) 가 주어진다.

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 Mk. For the assignment to succeed, it is important that the spies together know all the information obtained by the remaining spies.

입력

• The first line of input contains the positive integer N, the number of spies (2 ≤ N ≤ 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 Mk (1 ≤ Mk ≤ 10^6), the prices of sending each spy on the assignment, in order for spies 1, 2, ..., N.

출력

입출력 예

input 

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

output 

17 

input 

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

output 

34 

input 

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 

output

28

Clarification of the first example: We will organize meetings between spies 1 and 2, then 2 and 3, 
and send spy 2 on the assignment. 

Clarification of the second example: We will organize a meeting between spies 2 and 3, and send 
spies 1 and 2 on the assignment. 

Clarification of the third example: 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.

출처:CROATIAN olympiad 2013