Warning：本题暂时没有 spj。

一眼网络流。考虑怎么做。

考虑把行号和权值分别作为二分图的左右部，把列号作为边权，则此时要求构造一个合法的完美匹配，使得对任意两个不同的左部点 $a,b$，假设其右部分别对应 $u,v$，有

也就是，不存在

的结构。

对于一个左部点，我们试图选择一个尽可能小的边权；对于右部点，我们试图选择一个尽可能大的边权。

这个就是稳定婚姻算法了，可以看这篇介绍。