Background

After consideration by the administrators, we plan to store the community-provided testdata separately in the last Subtask. The score of these test points is 0, but failing any of them will be regarded as not passing this problem.

In this problem, there is an issue where the test point numbers in the judging records are mixed up. This is caused by a naming conflict in the community testdata. However, we guarantee that their relative order is not messed up.

Community testdata provider: @QwQcOrZ。

Problem Description

There is an $m \times n$ array $a_{i,j}$.
Define:

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

You need to compute $\sum\limits_{i=1}^n\sum\limits_{j=1}^nf(i,j)$。

Input Format

The first line contains two positive integers $m, n$。

In the next $m$ lines, each line contains $n$ positive integers representing $a_{i,j}$。

Output Format

Output one positive integer in one line, representing the answer。

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

564

Hint

[Sample 1 Explanation]

Take $f(3,5)$ as an example:

$$\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}$$

The table of $f(i,j)$ is given below. The entry in row $i$ and column $j$ represents $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}$$

Their sum is the answer $564$。

[Samples 2, 3, 4]

See sort/sort*.in and sort/sort*.ans in the contestant directory。

[Constraints and Hints]

For all test points: $2\le m\le 4$，$1\le n\le 2\times {10}^5$，$1\le a_{i,j}\le 2\times 10^5$。

The specific limits for each test point are shown in the table below。

::cute-table{tuack}

Test Point ID	$m =$	$n \le$
$1$	$4$	$3000$
$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$

Translated by ChatGPT 5