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 Bitmask DP (\(dp[mask]\) = chi phí nhỏ nhất để hoàn thành các việc ứng với bit 1 trong \(mask\)) để tìm tổng chi phí nhỏ nhất.

Input:

• 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\))

Output: Một số nguyên duy nhất — tổng chi phí nhỏ nhất.

Ví dụ: Input:

3
4 1 6
2 5 3
7 8 9

Output:

11