题目背景

翻译自 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

样例1解释

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

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

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

说明/提示

$1 \leq n \leq 200$；

$1 \leq c_{ij} \leq 1000$。