Ở một vùng bản xa xôi nọ, do ở rất xa so với thành phố nên người dân nơi đây không có điện để dùng, các em nhỏ học tập rất khó khăn.

Nhân dịp năm mới 2022, UTC đã chung tay đóng góp cùng các trường đại học khác để giúp đỡ xây dựng hệ thống điện trên bản làng này.

Để tránh lãng phí, các trường muốn tính toán xem số tiền nhỏ nhất để xây dựng hệ thống điện đến từng gia đình là bao nhiêu?

Bạn hãy giúp họ tính toán khoản tiền tối thiểu để cung cấp điện cho tât cả các hộ gia đình là bao nhiêu nhé!

Có N (1 <= N <= 300) hộ gia đình, muốn mắc điện lên 1 hộ gia đình ta có 2 cách:

Cách 1: Xây dựng 1 trạm phát điện tại hộ gia đình này.

Cách 2: Nối điện từ gia đình đã có điện tới.

Input:

• Dòng đầu tiên là số nguyên N

• N dòng tiếp theo là Xi, Xi+1, ... ,Xn lần lượt là chi phí để xây dựng trạm phát điện tại hộ gia đình thứ i. (1 <= Xi <= 10^5)

• N dòng tiếp theo, dòng thứ N + 1 + i (i = 1,2,...,N) chứa N số nguyên Pij lần lượt là phí để nối điện giữa hộ gia đình i và j. (1 <= Pij <= 10^5)

Output:

• Chi phí tối thiểu để tất cả các hộ gia đình đều có điện.

Example:

Input:

4
3
10
9
3
0 1 7 5 
1 0 7 10 
7 7 0 8 
5 10 8 0

Output:

14

Giải thích: Ta làm trạm phát điện tại hộ gia đình 1 và 4 hết tất cả 6 tiền, tiếp theo ta nối hộ gia đình 1 đến hộ gia đình 2 và 3 hết 1 + 7 = 8 tiền. Tổng tiền ít nhất phải trả là 14