Cho n thành phố đánh số từ 1 đến n và các tuyến đường giao thông hai chiều giữa chúng, mạng lưới giao thông này được cho bởi mảng ~C[1…n, 1…n]~ ở đây ~C[i][j]~ = ~C[j][i]~ là chi phí đi đoạn đường trực tiếp từ thành phố ~i~ đến thành phố ~j~. Một người du lịch xuất phát từ thành phố ~1~, muốn đi thăm tất cả các thành phố còn lại mỗi thành phố đúng 1 lần và cuối cùng quay lại thành phố 1. Hãy chỉ ra chi phí ít nhất mà người đó phải bỏ ra.

Đầu vào

Dòng đầu tiên là số nguyên ~n~ – số thành phố

~n~ dòng sau, mỗi dòng chứa ~n~ số nguyên thể hiện cho mảng 2 chiều ~C~.

Giới hạn

~1 \leq N \leq 15~

~0 \leq C[i][j] \leq 100~

Đầu ra

In ra chi phí mà người đó phải bỏ ra

Ví dụ :

Input 01

4
0 85 26 81 
85 0 77 97 
26 77 0 26 
81 97 26 0

Output 01

234