Tý có một người du lịch muốn đi thăm \(N\) thành phố (đánh số \(0\) đến \(N-1\)). Anh ta xuất phát từ thành phố \(0\), đi qua mỗi thành phố còn lại đúng một lần rồi quay về thành phố \(0\). Biết ma trận khoảng cách \(dist[i][j]\) giữa hai thành phố \(i\) và \(j\).

Hãy tìm hành trình có tổng khoảng cách ngắn nhất.

Định dạng đầu vào

• Dòng đầu chứa \(N\) (\(3 \le N \le 20\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(dist[i][j]\) (\(1 \le dist[i][j] \le 10^4\), \(dist[i][i] = 0\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng khoảng cách ngắn nhất tìm được.

Ví dụ

Input:

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

Output:

80

Ràng buộc