Phân Công Chi Phí Nhỏ Nhất

Một công ty có $n$ nhân viên và $n$ công việc. Chi phí để nhân viên $i$ thực hiện công việc $j$ là $c_i[j]$.

Hãy giao cho mỗi nhân viên đúng một công việc, đồng thời mỗi công việc cũng được giao cho đúng một nhân viên, sao cho tổng chi phí nhỏ nhất. Ngoài giá trị tối ưu, bạn phải in ra một phương án đạt được giá trị đó.

Input

• Dòng đầu chứa số nguyên $n$.
• Mỗi dòng trong $n$ dòng tiếp theo chứa $n$ số nguyên. Số thứ $j$ trên dòng thứ $i$ là $c_i[j]$.

Output

• Dòng đầu in tổng chi phí nhỏ nhất.

• Trong $n$ dòng tiếp theo, mỗi dòng in hai số nguyên $a$ $b$, nghĩa là giao công việc $b$ cho nhân viên $a$. Mỗi chỉ số nhân viên và mỗi chỉ số công việc phải xuất hiện đúng một lần.

• Nếu có nhiều phương án tối ưu, bạn có thể in bất kỳ phương án nào.

Constraints

• $1\le n\le 200$.
• $1\le c_i[j]\le 1000$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 9$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

3
9 2 7
6 4 3
5 8 1

9
1 2
2 1
3 3