题目背景

翻译自 CSES-2129 题。

题目描述

一家公司有 $n$ 个员工，且有 $n$ 个任务需要完成。我们知道每个员工执行每个任务的费用。每个员工必须被分配一个任务。请问，如何最优分配任务，使得总费用最小，并给出任务的具体分配方案。

输入格式

第一行包含一个整数 $n$：表示员工的数量，同时也表示任务的数量。

接下来的 $n$ 行中，每行包含 $n$ 个整数，表示每个员工执行每个任务的费用。第 $i$ 行中的第 $j$ 个整数 $c_{ij}$ 表示第 $i$ 个员工执行第 $j$ 个任务的费用。

输出格式

首先输出最小的总费用。

然后输出 $n$ 行，每行包含两个整数 $a$ 和 $b$，表示第 $a$ 个员工被分配了第 $b$ 个任务。

如果有多个最优解，可以输出任意一个。

样例

4
17 8 16 9
7 15 12 19
6 9 10 11
14 7 13 10

33
1 4
2 1
3 3
4 2

提示

最小的总费用是 $33$。我们可以通过以下分配方案达到最优：

• 第 $1$ 个员工执行第 $4$ 个任务，费用为 $9$；
• 第 $2$ 个员工执行第 $1$ 个任务，费用为 $7$；
• 第 $3$ 个员工执行第 $3$ 个任务，费用为 $10$；
• 第 $4$ 个员工执行第 $2$ 个任务，费用为 $7$。

总费用为 $9 + 7 + 10 + 7 = 33$。

数据范围

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