题目描述

有一个 $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}$。

输出格式

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

样例

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

样例 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*.in 与 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$。

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

测试点编号	m=	$n\leqslant$
1	4	3000
2	$2$	$10^{5}$
3~5	3
6~7	4	$5\times 10^{4}$
8~9		$10^{5}$
10		$2\times 10^{4}$