Mạng Kết Nối Dày

Có $n$ nút. Chi phí nối trực tiếp nút $i$ với nút $j$ được cho trong một ma trận đối xứng $c$ kích thước $n\times n$.

Hãy chọn một số kết nối sao cho mọi nút liên thông, đồng thời tổng chi phí là nhỏ nhất.

Input

• Dòng đầu chứa số nguyên $n$.
• Mỗi dòng trong $n$ dòng tiếp theo chứa $n$ số nguyên. Số thứ $j$ trên dòng thứ $i$ là $c_i[j]$.

Output

• In một số nguyên - tổng chi phí nhỏ nhất để nối toàn bộ nút.

Constraints

• $1\le n\le 1000$.
• $c_i[i]=0$.
• Với $i\ne j,1\le c_i[j]\le 10^8$.
• $c_i[j]=c_j[i]$.
• Đáp án có thể cần kiểu số nguyên $64$ bit.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 8$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

10