Du lịch

Sau khi tìm được kho báu, Anny sắp xếp một chuyến đi du lịch vòng quanh thế giới. Có \(N\) điểm du lịch Anny muốn ghé thăm, được đánh số từ \(1\) đến \(N\). Giữa các điểm du lịch có các chuyến bay đi trực tiếp; chi phí để bay từ điểm \(i\) đến điểm \(j\) là \(C_{ij}\) (có thể khác \(C_{ji}\)) và \(1 \le C_{ij} \le 10^9\).

Anny muốn chọn một hành trình du lịch qua \(N\) điểm, mỗi điểm chỉ ghé thăm một lần duy nhất. Với tinh thần tiết kiệm, Anny muốn chọn một hành trình du lịch với tổng chi phí nhỏ nhất.

Yêu cầu: Hãy giúp Anny tìm được hành trình có tổng chi phí nhỏ nhất.

Input

Dữ liệu vào có cấu trúc như sau:

• Dòng đầu ghi số nguyên dương \(N\);

• Dòng thứ \(i\) trong \(N\) dòng tiếp theo, ghi \(N\) số nguyên không âm \(C_{ij}\) là chi phí bay từ điểm \(i\) đến điểm \(j\) (\(1 \le j \le N\)).

Ràng buộc:

• Có \(50\%\) số test ứng với \(50\%\) số điểm có: \(5 < N \le 10\);

• Có \(50\%\) số test ứng với \(50\%\) số điểm có: \(10 < N \le 15\).

Output

In ra một số nguyên dương duy nhất là tổng chi phí của hành trình nhỏ nhất tìm được.

Example

Input:

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

Output:

8

Note

Hành trình có thể bắt đầu ở điểm bất kỳ và kết thúc ở điểm bất kỳ (không cần quay về điểm xuất phát), mỗi điểm được ghé thăm đúng một lần.