Xếp quân hậu tổng lớn nhất


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.