链接: https://cses.fi/problemset/task/2129

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一家公司拥有 $n$ 名员工，并且有 $n$ 项任务需要完成。我们知道每名员工完成每项任务的成本。每名员工应恰好分配到一项任务。在最优化分配的情况下，最小的总成本是多少？又该如何分配？

输入

第一行有一个整数 $n$：员工数量以及需要完成的任务数量。

之后有 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行包含整数 $c_{i1},c_{i2},\ldots,c_{in}$：将各项任务分配给第 $i$ 名员工时的成本。

输出

先输出最小总成本。

然后输出 $n$ 行，每行两个整数 $a$ 和 $b$：将第 $b$ 项任务分配给第 $a$ 名员工。

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

数据范围

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

样例输入

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