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}$. Tìm cách phân công sao cho tổng chi phí nhỏ nhất, và in ra cách phân công đó.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ — số công nhân và số công việc.

• $n$ dòng tiếp theo, mỗi dòng chứa $n$ số nguyên $c_{i1},c_{i2},\dots ,c_{in}$ — chi phí cho công nhân $i$ thực hiện từng công việc.

Dữ liệu ra

Dòng đầu tiên 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$ — công nhân $a$ được giao công việc $b$.

Ràng buộc

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

Ví dụ