Ở vương quốc nọ, có một vị vua và ông có ~ n ~ quý phi. Trên miếng đất hình vuông kích thước ~ n×n ~, nhà vua muốn xây dựng cho mỗi quý phi, mỗi người một cung điện (giả sử mỗi cung điện đều nằm trên 1 ô đất kích thước ~ 1×1 ~). Vấn đề là các quý phi này có tính ghen ghét nhau nên nhà vua không muốn các cung điện nhìn thấy nhau từ các hướng (ngang, dọc, chéo). Chi phí xây dựng các cung điện trên mỗi ô đất có thể có giá thành khác nhau, nhà vua muốn xây dựng ~ n ~ cung điện tổng tính chi phí thấp nhất.

Yêu cầu: Bạn hãy giúp nhà vua thực hiện công việc đó.

Dữ liệu vào

• Dòng đầu chứa số ~ n ~ ~ (1 ≤ n ≤ 16) ~
• ~ n ~ dòng sau, mỗi dòng chứa n số là chi phí xây dựng tại ô đất tương ứng (chi phí xây dựng cung điện trong một ô có giá trị nguyên từ 1 tới 1000). Mỗi số cách nhau ít nhất một khoảng trắng.

Kết quả

Một số duy nhất cho biết tổng chi phí thấp nhất cho việc xây dựng. Giả sử dữ liệu đã cho luôn có lời giải.

Ví dụ:

Input 1

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

Output 1

15