Bài toán người bán hàng 2

Có \(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\) (\(1 \le n \le 20\)).

• \(n\) dòng tiếp theo, mỗi dòng gồm \(n\) số nguyên \(A_{i,j}\) (\(0 \le A_{i,j} \le 1000\)).

Output

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

Example

Input:

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

Output:

0