[TJOI2014]匹配

题目描述

有N个单身的男孩和N个单身女孩,男孩i和女孩j在一起得到的幸福值为Hij。一个匹配即对这N个男孩女孩的安排:每个男孩恰好有一个女朋友每个女孩恰好有一个男朋友。 一个匹配的幸福值即这N对男女朋友的幸福值的和。经典的问题是计算幸福值最大的匹配,即完美匹配。然而完美匹配有时候并不唯一,你需要计算对于所有的完美匹配,其交集是什么。

输入输出格式

输入格式


输入的第一行是一个正整数N。接下来是一个N\*N大小的矩阵H,Hij表示男孩i和女孩j在一起的幸福值。(0≤Hij≤5000)

输出格式


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

输入输出样例

输入样例 #1

3
1 1 1
2 1 1
1 1 1

输出样例 #1

4
2 1

说明

### 数据范围 对于 30% 的数据,N ≤ 30 对于 100% 的数据,N ≤ 80