Bài Toán Phân Công

Có $n$ công nhân và $n$ công việc. Mỗi công nhân phải thực hiện đúng một công việc, và mỗi công việc phải được giao cho đúng một công nhân.

Chi phí để công nhân $i$ thực hiện công việc $j$ là $c_{ij}$. Hãy tìm cách phân công có tổng chi phí nhỏ nhất và in ra cách phân công đó.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số công nhân, cũng là số công việc.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số nguyên $c_{i1},c_{i2},\dots ,c_{in}$ là chi phí để công nhân $i$ thực hiện từng công việc.

Dữ liệu ra

• Dòng đầu in tổng chi phí nhỏ nhất.
• $n$ dòng tiếp theo, mỗi dòng in hai số nguyên $a$ và $b$ cho biết công nhân $a$ được giao công việc $b$. Mỗi công nhân và mỗi công việc phải xuất hiện đúng một lần, và tổng chi phí của cách phân công in ra phải đúng bằng số ở dòng đầu.

Các dòng phân công có thể in theo thứ tự bất kỳ. Nếu có nhiều cách phân công cùng đạt chi phí nhỏ nhất, in ra một cách bất kỳ.

Ràng buộc

• $1\le n\le 200$
• $1\le c_{ij}\le 1000$

Ví dụ