题目描述

对于两个集合$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$。然后，令$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 = \lbrace A_{i,1},A_{i,2},\dots,A_{i,M}\rbrace$。这里，保证$S_i \cap S_j = \emptyset\ (i \neq j)$。

找到$\\sum_{1\leq i<j \leq N} f(S_i, S_j)$ 的值。

约束条件

• $1\leq N \leq 10^4$
• $1\leq M \leq 10^2$
• $1\leq A_{i,j} \leq 10^9$
• 如果$i_1 \neq i_2$或$j_1 \neq j_2$，则$A_{i_1,j_1} \neq A_{i_2,j_2}$。
• 所有输入值均为整数。

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,M}$ $\vdots$ $A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,M}$

输出

将答案作为整数打印出来。

示例输入1

3 2
1 3
2 8
4 6

示例输出1

12

$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$。

示例输入2

1 1
306

示例输出2

0

示例输入3

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

示例输出3

102