Hành trình rẻ nhất

Một nhà thám hiểm muốn ghé thăm đủ \(N\) thành phố, được đánh số từ \(1\) đến \(N\), bằng đường hàng không. Anh ta được tự do chọn thành phố xuất phát, sau đó bay lần lượt qua các thành phố còn lại sao cho mỗi thành phố được ghé đúng một lần (không cần quay về điểm đầu).

Giá vé bay thẳng từ thành phố \(i\) đến thành phố \(j\) là \(c_{i,j}\) (giá vé chiều đi và chiều về có thể khác nhau). Hãy tìm tổng tiền vé nhỏ nhất của một hành trình như vậy.

Input

• Dòng đầu chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(N\) số nguyên \(c_{i,1}, c_{i,2}, \dots, c_{i,N}\).

Output

In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Constraints

• \(1 \le N \le 16\).
• \(c_{i,i} = 0\); với \(i \ne j\) thì \(1 \le c_{i,j} \le 10^9\).

Sample Input

4
0 3 1 5
2 0 4 1
6 2 0 3
1 7 2 0

Sample Output

3

Explanation

Hành trình \(2 \to 4 \to 1 \to 3\) có tổng chi phí \(1 + 1 + 1 = 3\).