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

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

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

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

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

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

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

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

天津省选