Cho N thành phố đôi một nối với nhau với độ dài đường đi xác định tạo thành một đồ thị vô hướng đầy đủ có trọng số dương. Bạn hãy lập trình tìm một hành trình đi du lịch qua tất cả các thành phố mỗi thành phố đúng 1 lần rồi trở về đỉnh xuất phát sao cho tổng quãng đường đi là nhỏ nhất.

Input

Dòng đầu tiên chứa số nguyên dương N \((N \le 15)\) số thành phố

N dòng tiếp theo mỗi dòng chứa N số nguyên không vượt quá 100 là ma trận kề biểu diễn khoảng cách giữa cặp các thành phố

Output

Một số nguyên dương là trọng số nhỏ nhất của hành trình phải đi của người đi du lịch

Example 1

Input

4
0 8 6 5
8 0 4 4 
6 4 0 3
5 4 3 0

Output

19

Giải thích: Hành trình ngắn nhất 1->3->2->4->1