Xếp quân hậu tổng lớn nhất
Cho một bàn cờ $N \times N$. Ô ở hàng thứ $i$ và cột thứ $j$ có giá trị $a_{i,j}$. Tìm cách xếp $N$ quân hậu trên bàn cờ sao cho tổng giá trị các ô đặt quân hậu là lớn nhất.
Dữ liệu
- Dòng đầu tiên chứa số nguyên $N \ (1\le N \le 12)$;
- $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên $a_{i,j} \ (1\le a_{i,j} \le10^9)$.
Kết quả
- Tổng lớn nhất đó.
Ví dụ
Ví dụ 1
input
8
6 4 9 8 1 3 4 6
6 8 9 8 4 4 6 4
9 4 9 7 6 5 2 6
1 7 10 7 8 2 9 7
4 4 7 4 1 5 7 4
9 9 7 4 7 6 8 8
2 9 9 2 3 8 7 9
4 1 9 3 5 1 5 6
output
62
Comments