min-max 容斥。先排序，从小到大填进去。
设
A1,A2,…An 为每一行被填满的时候的最大的值（即最后一个被填进去的那个数）；
B1,B2,…,Bn 为 每一列被填满的时候的最大的值。那么一种方案的答案就是
min({A1,A2,…,An}∪{B1,B2,…Bn})=∑S⊂{A1,A2,…,An}∑T⊂{B1,B2,…Bn}(−1)∣S∣+∣T∣+1max(S∪T)
你发现这个
max(S∪T) 在做的事情就是选定某些特定的行和列，求出这些格子里最后被填进去的数是什么。容易发现这个值只和被考虑到的格子数量有关，而这个格子数量只和
∣S∣,∣T∣ 有关。因此我们可以改写这个式子为：
∑i=0n∑j=0m(−1)i+j+1(in)(jm)f(im+jn−ij)
f(x) 表示考虑
x 个格子。容易发现选中
i 行
j 列，会考虑到
im+jn−ij 个格子。
这个式子复杂度已经对了，现在唯一的问题是算
f(t)。考虑枚举最后一个填进去的数是什么：
f(t)=∑i=1nmai(t−1i−1)t!(nm−t)!
这个式子的意义就是第
i 个数是最有一个填进去的，前
i−1 个数里挑
t−1 填到剩下
t−1 个格子里，这
t 个数和剩下的
nm−t 个数分别可以随便排序，所以乘上阶乘。
这个式子可以差卷积。做完了。