Hệ thống nước

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: một là đào ở đồng cỏ đó $1$ cái giếng, hai là lắp ống nối dẫn nước từ một đồng cỏ khá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 100000$). 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 100000$ với $i\ne j$; $P_{ij}=P_{ji}$; $P_{ii}=0$).

Nước chảy được theo cả hai chiều của ống và qua nhiều ống liên tiếp, nên một đồng cỏ có nước nếu tại đó có giếng hoặc từ đó đi theo các ống đã lắp tới được một đồng cỏ có giếng. Thứ tự lắp đặt không quan trọng: "đồng cỏ đã có nước" không phụ thuộc vào số thứ tự của đồng cỏ (xem ví dụ $1$, nước đi từ đồng cỏ $4$ sang đồng cỏ $1$ rồi sang các đồng cỏ $2$, $3$).

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.

Dữ liệu vào

• 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}$.

Dữ liệu ra

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ỏ.

Ràng buộc

• $1\le N\le 300$.
• $1\le W_i\le 100000$.
• $1\le P_{ij}\le 100000$ với $i\ne j$; $P_{ij}=P_{ji}$; $P_{ii}=0$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $N\le 100$, $W_i\le {10}^2$, $P_{ij}\le {10}^2$.
• Subtask 2 ($30\%$ số điểm): $N\le 200$, $W_i\le {10}^3$, $P_{ij}\le {10}^3$.
• Subtask 3 ($40\%$ số điểm): $N\le 300$, $W_i\le {10}^5$, $P_{ij}\le {10}^5$.

Ví dụ