#5172. 如何正确地排序

如何正确地排序

题目描述

有一个 m×nm \times n 的数组 ai, ja_{i,~j}

定义:

$$f(i,~j) = \min_{k = 1} ^ m (a_{k,~i} + a_{k,~j}) + \max_{k = 1} ^ m (a_{k,~i} + a_{k,~j}) $$

你需要求出 i=1nj=1nf(i, j)\sum_{i = 1}^n \sum_{j = 1}^n f(i,~j)

输入格式

第一行两个正整数 m, nm,~n

接下来 mm 行,每行 nn 个正整数表示 ai, ja_{i,~j}

输出格式

一行一个正整数,表示答案。

3 5
1 7 2 2 7
9 10 4 10 3
7 7 8 10 2
564

样例 1 解释

f(3, 5)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)f(i,~j) 的表,第 ii 行第 jj 列表示 f(i, j)f(i,~j)

20 27 18 22 20
27 34 24 29 23
18 24 20 22 17
22 29 22 24 22
20 23 17 22 18

他们的和是答案 564564

输入输出数据 2

sort2.insort2.ans

输入输出数据 3

sort3.insort3.ans

输入输出数据 4

sort4.insort4.ans

数据范围

对于所有测试点:$2 \le m \le 4,~1 \le n \le 2 \times 10^5,~1 \le a_{i,~j} \le 2 \times 10^5$。

每个测试点的具体限制见下表:

测试点编号 m=m = nn \le
11 44 30003000
22 22 10510^5
353 \sim 5 33
676 \sim 7 44 5×1045 \times 10^4
898 \sim 9 10510^5
1010 2×1052 \times 10^5