Ở vương quốc nọ có một vị vua và N quí phi. Trên miếng đất hình vuông kích thước N x N, nhà vua muốn xây cho các quí phi, mỗi người một cung điện (giả sử mỗi cung điện đều nằm trên một ô đất kích thước 1 x 1). Vấn đề là các quí phi đều rất 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ó các giá trị khác nhau, nhà vua muốn xây dựng N cung điện với 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 ≤ 12)
• N dòng tiếp theo, mỗi dòng chứa N số là chi phí xây dựng của ô tương ứng (chi phí xây dựng cung điện trong ô có giá trị từ 1 đến 1000). Mỗi số cách nhau 1 khoảng trắng.

Kết quả: Một số là chi phí nhỏ nhất xây dựng N cung điện