Mô tả và yêu cầu

Ở 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 NxN, 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 một ô đất kích thước 1x1). 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, và 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 với tổng 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ữ liệu vào từ thiết bị nhập chuẩn gồm N+1 dòng:
- Dòng đầu chứa số N.
- 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. Mỗi số cách nhau ít nhất một khoảng trống.

Dữ liệu ra

Kết quả ghi ra file thiết bị xuất chuẩn gồm 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ới hạn và chấm điểm

1≤N≤16
Chi phí xây dựng cung điện trong một ô có giá trị nguyên từ 1 đến 1000.
Giả sử dữ liệu đã cho luôn có lời giải.

Ví dụ

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

15

Các ô đất được chọn là các ô tô đậm, có tổng chi phí là 15.
3 4 12 3
6 1 7 1
2 4 1 5
12 3 8 7