Nông dân John quyết định mang nước tới cho ~N~ (~1 \leq N \leq 300~) đồng cỏ của mình, để thuận tiện ta đánh số các đồng cỏ từ ~1~ đến ~N~. Để tưới nước cho ~1~ đồng cỏ John 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 \leq~ ~W_i~ ~\leq 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 \leq~ ~P_{ij}~ ~\leq 100000~; ~P_{ij} = P_{ji}; P_{ii}=0)~.

Tính xem nông dân John 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 ~1~: Một số nguyên duy nhất: ~N~
• Các dòng ~2~.. ~N~ + ~1~: Dòng ~i+1~ chứa ~1~ số nguyên duy nhất: ~W_i~
• Các dòng ~N+2~.. ~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

• Dòng ~1~: 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

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

Sample Output

9

Note

Có 4 đồng cỏ. Mất 5 tiền để đào 1 cái giếng ở đồng cỏ 1, 4 tiền để đào ở đồng cỏ 2, 3 và 3 tiền để đào ở đồng cỏ 4. Các ống dẫn nước tốn 2, 3, và 4 tiền tùy thuộc vào nó nối đồng cỏ nào với nhau.

Nông dân John có thể đào 1 cái giếng ở đồng cỏ thứ 4 và lắp ống dẫn nối đồng cỏ 1 với tất cả 3 đồng cỏ còn lại, chi phí tổng cộng là 3 + 2 + 2 + 2 = 9.