题目描述

有一个 $m \times n$ 的数组 $a_{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}) $$

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

输入格式

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

接下来 $m$ 行，每行 $n$ 个正整数表示 $a_{i,~j}$。

输出格式

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

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

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)$：

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

他们的和是答案 $564$。

输入输出数据 2

见 sort2.in 和 sort2.ans。

输入输出数据 3

见 sort3.in 和 sort3.ans。

输入输出数据 4

见 sort4.in 和 sort4.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 =$	$n \le$
$1$	$4$	$3000$
$2$	$2$	$10^5$
$3 \sim 5$	$3$
$6 \sim 7$	$4$	$5 \times 10^4$
$8 \sim 9$		$10^5$
$10$		$2 \times 10^5$