Gán Công Việc Bitmask

Cho một ma trận chi phí $C$ kích thước $N\times N$. $C[i][j]$ là chi phí khi gán công nhân $i$ làm công việc $j$.

Bạn phải gán mỗi công nhân đúng một công việc và mỗi công việc được đúng một công nhân. Hãy tìm tổng chi phí nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$.
• $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên. Dòng $i+1$ chứa $C[i][0],C[i][1],\dots ,C[i][N-1]$.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng chi phí nhỏ nhất.

Ràng buộc

• $1\le N\le 16$
• $1\le C[i][j]\le {10}^9$

Ví dụ

Ghi chú

Đây là bài toán gán (assignment problem) phiên bản nhỏ: có thể giải bằng bitmask DP với độ phức tạp $O(N·2^N)$.