Universal Online Judge
UOJ
时间限制:N/A
空间限制:N/A
Statistics
## 题目描述
有$N$个单身的男孩和$N$个单身女孩，男孩$i$和女孩$j$在一起得到的幸福值为$H_{i,j}$。
一个匹配即对这$N$个男孩女孩的安排：每个男孩恰好有一个女朋友，每个女孩恰好有一个男朋友。
一个匹配的幸福值即这$N$对男女朋友的幸福值的和。
经典的问题是计算幸福值最大的匹配，即完美匹配。然而完美匹配有时候并不唯一，你需要计算对于所有的完美匹配，其交集是什么。
## 输入输出格式
### 输入格式
输入的第一行是一个正整数$N$。
接下来是一个$N imes N$大小的矩阵$H$，$H_{i,j}$表示男孩$i$和女孩$j$在一起的幸福值。
### 输出格式
第一行输出完美匹配的幸福值，接下来是若干行，每一行是一对整数$i$和$j$，表示男孩$i$和女孩$j$在所有完美匹配的交集中，以$i$的递增顺序输出。
## 输入输出样例
### 输入样例 #1
```
3
1 1 1
2 1 1
1 1 1
```
### 输出样例 #1
```
4
2 1
```
## 说明/提示
- 对于$30\%$的数据，$N leq 30$；
- 对于$100\%$的数据，$1leq N leq 80$，$0leq H_{i,j}leq 5 imes10^3$。