Công ty của Bảo có \(N\) nhân viên và N công việc khác nhau. Mỗi nhân viên chỉ làm đúng 1 việc, mỗi việc chỉ giao cho 1 người. Ma trận \(\text{cost}[i][j]\) là chi phí khi giao việc j cho nhân viên \(i\).

Hãy dùng phương pháp Quy hoạch động trạng thái Bitmask (\(dp[mask] = chi phí nhỏ nhất để hoàn thành tập các công việc tương ứng với các bit 1 trong mask\)) để tìm tổng chi phí phân công nhỏ nhất.

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(1 \le N $\le 15\)).
• \(N\) dòng tiếp theo: mỗi dòng gồm N số nguyên \(\text{cost}[i][j]\) (\(1 \le \text{cost}[i][j] $\le 100\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng chi phí nhỏ nhất tìm được.

Ví dụ

Input:

3
4 1 6
2 5 3
7 8 9

Output:

11

Giải thích: Phân công người 1 làm việc 2 (chi phí 1), người 2 làm việc 1 (chi phí 2), người 3 làm việc 3 (chi phí 8). Tổng chi phí: \(1 + 2 + 8 = 11\).

Ràng buộc & Subtasks