#762. Khởi đầu mới (WATER)

Phát triển ngành khai thác mỏ đương nhiên trước hết phải có mỏ. Tiểu FF đã tiêu tốn một phần nghìn tài sản từ chuyến thám hiểm lần trước để thuê người đào mỏ quặng trên đảo, nhưng cậu ấy dường như quên mất vấn đề cung cấp điện cho các mỏ...

Để đảm bảo cung cấp điện, Tiểu FF nghĩ ra hai cách:

1. Xây dựng một trạm phát điện ngay tại mỏ đó, chi phí là (công suất đầu ra của trạm phát có thể cung cấp cho tùy ý bao nhiêu mỏ khác).
2. Xây dựng lưới điện kết nối mỏ này với một mỏ khác đã có điện, chi phí là .

Tiểu FF hy vọng bạn, với tư cách là kỹ sư trưởng của dự án "NewBe_One", sẽ giúp cậu ấy tìm ra chi phí tối thiểu để đảm bảo cung cấp điện cho tất cả các mỏ.

Dữ liệu:

• Dòng đầu tiên là một số nguyên , biểu thị tổng số mỏ quặng.
• Các dòng từ , mỗi dòng một số nguyên, số thứ là biểu thị chi phí xây trạm phát điện tại mỏ thứ .
• Tiếp theo là một ma trận kích thước , trong đó biểu thị chi phí xây dựng lưới điện giữa mỏ thứ và mỏ thứ (dữ liệu đảm bảo và ).

Kết quả:

• Xuất ra duy nhất một số nguyên, biểu thị chi phí tối thiểu để tất cả các mỏ đều có đủ điện năng.

Ví dụ:

Dữ liệu:

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

Kết quả:

9

Giới hạn:

• Với 30% dữ liệu: .
• Với 100% dữ liệu: .