当前没有测试数据。

题目描述

对于两个整数集合 $A$ 和 $B$ ，使得 $A \cap B = \emptyset$ ，我们定义 $f(A,B)$ 如下。

• 设 $C=(C_1,C_2,\dots,C_{|A|+|B|})$ 是由 $A \cup B$ 的元素组成的序列，按升序排序。
• 取 $k_1,k_2,\dots,k_{|A|}$ 这样的 $A=\lbrace C_{k_1},C_{k_2},\dots,C_{k_{|A|}}\rbrace$ 。那么，设 $\displaystyle f(A,B)=\sum_{i=1}^{|A|} k_i$ .

例如，如果 $A=\lbrace 1,3\rbrace$ 和 $B=\lbrace 2,8\rbrace$ ，那么 $C=(1,2,3,8)$ ，所以 $A=\lbrace C_1,C_3\rbrace$ ；因此， $f(A,B)=1+3=4$ 。

我们有 $N$ 个整数集合， $S_1,S_2\dots,S_N$ ，每个集合有 $M$ 个元素。

对于每个 $i (1 \leq i \leq N)$ , $S_i = \{A_{i,1},A_{i,2},\dots,A_{i,M}\}$。这里保证有 $S_i \cap _j = \emptyset (i \neq j)$ 个元素。

求 $\displaystyle \sum_{1\leq i<j \leq N} f(S_i, S_j)$ .

输入格式

第一行输入 $N$ $M$

第二行输入 $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,M}$

第三行输入 $A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,M}$

$\vdots$

第 $N+1$ 行输入 $A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,M}$

输出格式

输出一个整数代表答案

3 2
1 3
2 8
4 6

12

1 1
306

0

4 4
155374934 164163676 576823355 954291757
797829355 404011431 353195922 138996221
191890310 782177068 818008580 384836991
160449218 545531545 840594328 501899080

102

提示

数据范围

• $1\leq\ N\ \leq\ 10^4$
• $1\leq\ M\ \leq\ 10^2$
• $1\leq\ A_{i,j}\ \leq\ 10^9$
• $N\times M$ 个数字均互不相同。

Sample Explanation 1

$S_1$ 和 $S_2$ 分别与问题陈述中例举的 $A$ 和 $B$ 以及 $f(S_1,S_2)=1+3=4$ 重合。因为 $f(S_1,S_3)=1+2=3$ 和 $f(S_2,S_3)=1+4=5$ ，所以答案为 $4+3+5=12$ 。