Bạn là ~M~, người đứng đầu cơ quan tình báo tuyển dụng ~N~ điệp viên với mật danh từ ~1~ đến ~N~.

Mỗi điệp viên được chỉ định đến một quốc gia khác nhau và thu được một thông tin quan trọng ở đó. Nhiệm vụ của bạn là như sau:

1. Tổ chức các cuộc gặp gỡ giữa một số điệp viên. Trong mỗi cuộc gặp, có đúng hai điệp viên gặp nhau và trao đổi tất cả những thông tin mà họ có được hoặc học được từ các điệp viên khác trong những lần gặp trước. Việc tổ chức một cuộc gặp tuyệt mật giữa hai điệp viên ở các quốc gia khác nhau rất khó khăn nên mỗi cuộc gặp tiềm năng đều có cái giá của nó.

2. Sau khi tất cả các cuộc họp kết thúc, hãy chọn một nhóm điệp viên nhỏ và cử họ cùng nhau thực hiện nhiệm vụ cứu thế giới (và tán tỉnh phụ nữ). Gửi một điệp viên ~k~ đi làm nhiệm vụ có giá ~M_k~. Để nhiệm vụ thành công, điều quan trọng là các điệp viên phải cùng nhau biết tất cả thông tin mà các điệp viên còn lại thu được.

Tìm tổng chi phí tối thiểu để chuẩn bị và thực hiện nhiệm vụ này.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~, số lượng gián điệp ~(2 ≤ N ≤ 1000)~.
• ~N~ dòng tiếp theo, mỗi ~N~ dòng chứa ~N~ số nguyên dương không vượt quá ~10^6~. Số ở hàng ~k~ và cột ~m~ là giá của cuộc gặp gỡ giữa điệp viên ~k~ và ~m~ và tất nhiên bằng số ở hàng ~m~ và cột ~k~ (với ~k = m~ số sẽ là ~0~).
• Dòng tiếp theo chứa ~N~ số nguyên dương ~M_k~ ~(1 \le M_k \le 10^6)~, giá của mỗi điệp viên đi làm nhiệm vụ, theo thứ tự cho các điệp viên ~1, 2, ..., N~.

Output

• Dòng đầu tiên và duy nhất của đầu ra phải chứa tổng giá tối thiểu bắt buộc.

Scoring

• Trong dữ liệu thử nghiệm có ~N ≤ 30~, có tổng điểm là ~40~, sẽ tối ưu nếu gửi tối đa bốn điệp viên đi làm nhiệm vụ.
• Trong dữ liệu thử nghiệm có tổng điểm là ~50~, tất cả giá gửi điệp viên đi làm nhiệm vụ đều bằng nhau.

Sample Input 1

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

Sample Output 1

17

Sample Input 2

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

Sample Output 2

34

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

Giải thích:

• Làm rõ test ~1~: Chúng tôi sẽ tổ chức các cuộc họp giữa điệp viên ~1~ và ~2~, sau đó là ~2~ và ~3~, và cử điệp viên ~2~ đi làm nhiệm vụ.
• Làm rõ test ~2~: Chúng tôi sẽ tổ chức một cuộc gặp giữa điệp viên ~2~ và ~3~, đồng thời cử điệp viên ~1~ và ~2~ đi làm nhiệm vụ.
• Làm rõ test ~3~: Chúng tôi sẽ tổ chức các cuộc họp giữa điệp viên ~2~ và ~4~, sau đó là ~1~ và ~2~, rồi ~3~ và ~5~, đồng thời cử điệp viên ~1~ và ~3~ (hoặc ~1~ và ~5~) đi làm nhiệm vụ.