题目描述

一家公司有 $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

样例说明

一种最优方案是员工 $1$ 做任务 $4$，员工 $2$ 做任务 $1$，员工 $3$ 做任务 $3$，员工 $4$ 做任务 $2$，总代价为 $9+7+10+7=33$。