题目描述

有 $N$ 个单身的男孩和 $N$ 个单身女孩，男孩 $i$ 和女孩 $j$ 在一起得到的幸福值为 $H_{i,j}$。

一个匹配即对这 $N$ 个男孩女孩的安排：每个男孩恰好有一个女朋友，每个女孩恰好有一个男朋友。

一个匹配的幸福值即这 $N$ 对男女朋友的幸福值的和。

经典的问题是计算幸福值最大的匹配，即完美匹配。然而完美匹配有时候并不唯一，你需要计算对于所有的完美匹配，其交集是什么。

输入格式

输入的第一行是一个正整数 $N$ 。

接下来是一个 $N\times N$ 大小的矩阵 $H$，$H_{i,j}$ 表示男孩 $i$ 和女孩 $j$ 在一起的幸福值。

输出格式

第一行输出完美匹配的幸福值，接下来是若干行，每一行是一对整数 $i$ 和 $j$，表示男孩 $i$ 和女孩 $j$ 在所有完美匹配的交集中，以 $i$ 的递增顺序输出。

3
1 1 1
2 1 1
1 1 1

4
2 1

提示

• 对于 $30\%$ 的数据，$N \leq 30$；
• 对于 $100\%$ 的数据，$1\leq N \leq 80$，$0\leq H_{i,j}\leq 5\times10^3$。