Nhà bác Sơn ở huyện Mộc Châu – Sơn La có một trang trại nuôi bò sữa lớn. Để cung cấp đủ thức ăn cho bò, bác phải trồng rất nhiều cỏ. Mùa hè năm nay, bác đã quyết định làm một hệ thống tưới nước cho ~N~ (~1 \le N \le 300~) đồng cỏ của mình. Để thuận tiện, các đồng cỏ được đánh số từ 1 đến ~N~. Để tưới nước cho một đồng cỏ, bác có thể chọn 2 cách: 1 là đào ở đồng cỏ đó 1 cái giếng hoặc lắp ống nối dẫn nước từ những đồng cỏ trước đó đã có nước tưới.

Để đào một cái giếng ở đồng cỏ ~i~ cần 1 số tiền là ~W_i~ (~1 \le W_i \le 100.000~). Lắp ống dẫn nước nối 2 đồng cỏ ~i~ và ~j~ cần 1 số tiền là ~P_{ij}~ (~1 \le P_{ij} \le 100.000~; ~P_{ij} = P_{ji}~; ~P_{ii} = 0~).

Yêu cầu: Tính xem bác Sơn phải chi ít nhất bao nhiêu tiền để tất cả các đồng cỏ đều có nước.

Input

• Dòng đầu tiên ghi số nguyên dương ~N~ là số đồng cỏ.
• Các dòng ~2 \dots N+1~: Dòng ~i+1~ chứa một số nguyên duy nhất ~W_i~.
• Các dòng ~N+2 \dots 2N+1~: Dòng ~N+1+i~ chứa ~N~ số nguyên cách nhau bởi dấu cách; số thứ ~j~ là ~P_{ij}~.

Output

• Ghi ra một số nguyên duy nhất là chi phí tối thiểu để cung cấp nước cho tất cả các đồng cỏ.

Sample Input 1

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

Sample Output 1

9