[NOI Online 2022 提高组] 如何正确地排序
题目背景
**经过管理员的考虑,我们打算将民间数据单独存放在最后一个 Subtask 中。这些测试点分数均为 0 分,但是没有通过其中的任何测试点将会视为此题不通过。**
**这一题中出现了评测记录测试点编号错乱的问题,是民间数据命名方式冲突导致的。但是我们保证其相对顺序没有混乱。**
民间数据提供者:@QwQcOrZ。
题目描述
有一个 $m\times n$ 的数组 $a_{i,j}$。
定义:
$$f(i,j)=\min\limits_{k=1}^m(a_{k,i}+a_{k,j})+\max\limits_{k=1}^m(a_{k,i}+a_{k,j})$$
你需要求出 $\sum\limits_{i=1}^n\sum\limits_{j=1}^nf(i,j)$。
输入输出格式
输入格式
第一行两个正整数 $m,n$。
接下来 $m$ 行,每行 $n$ 个正整数表示 $a_{i,j}$。
输出格式
一行一个正整数,表示答案。
输入输出样例
输入样例 #1
3 5
1 7 2 2 7
9 10 4 10 3
7 7 8 10 2
输出样例 #1
564
说明
**【样例 1 解释】**
以 $f(3,5)$ 为例:
$$\begin{aligned}f(3,5)&=\max(a_{1,3}+a_{1,5},a_{2,3}+a_{2,5},a_{3,3}+a_{3,5})+\min(a_{1,3}+a_{1,5},a_{2,3}+a_{2,5},a_{3,3}+a_{3,5})\\&=\max(9,7,10)+\min(9,7,10)\\&=10+7\\&=17\end{aligned}$$
下面给出 $f(i,j)$ 的数表,第 $i$ 行第 $j$ 列表示 $f(i,j)$:
$$\begin{array}{|c|c|c|c|c|}\hline20&27&18&22&20\\\hline27&34&24&29&23\\\hline18&24&20&22&17\\\hline22&29&22&24&22\\\hline20&23&17&22&18\\\hline\end{array}$$
它们的和是答案 $564$。
**【样例 2, 3, 4】**
见选手目录下的 `sort/sort*.in` 与 `sort/sort*.ans`。
**【数据范围与提示】**
对于所有测试点:$2\le m\le 4$,$1\le n\le 2\times {10}^5$,$1\le a_{i,j}\le 2\times 10^5$。
每个测试点的具体限制见下表
![](https://cdn.luogu.com.cn/upload/image_hosting/h38vdmnj.png)