Cho \(n\) thành phố, di chuyển từ thành phố \(i\) sang thành phố \(j\) hết \(A_{i,j}\) xu. Hãy tìm lộ trình tốn ít tiền nhất để đi qua mỗi thành phố chính xác \(1\) lần và quay lại thành phố bắt đầu.

Input

• Dòng đầu tiên gồm số nguyên \(n\).
• \(n\) dòng tiếp theo, mỗi dòng gồm nsố nguyên \(A_{i,j}\).

Output

• Một số nguyên là lượng tiền ít nhất phải bỏ ra.

Điều kiện

• \(1 \le n \le 10\)
• \(1 \le A_{i,j} \le 1000\)

Sample Input 1

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

Sample Output 1

17