AT_abc306_f.[ABC306F] Merge Sets

对于满足 $A \cap B = \emptyset$ 的两个整数集合 $A, B$，定义 $f(A,B)$ 如下：

• 将 $A \cup B$ 中的元素按升序排列，得到数列 $C=(C_1,C_2,\dots,C_{|A|+|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)$。

请计算 $\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$
$A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,M}$

请输出答案的整数值。

限制条件

• $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}$
• 输入均为整数

样例解释 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$ 是答案。

由 ChatGPT 4.1 翻译