当前没有测试数据。

F - 合并集合

得分：$525$ 点

问题描述

对于两个集合 $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=\{C_{k_1},C_{k_2},\dots,C_{k_{|A|}}\}$。 然后，定义 $\displaystyle f(A,B)=\sum_{i=1}^{|A|} k_i$。

例如，如果 $A=\{1,3\}$，$B=\{2,8\}$，那么 $C=(1,2,3,8)$，因此 $A=\{C_1,C_3\}$；因此，$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 S_j = \emptyset\ (i \neq j)$。

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

输出

输出一个整数作为答案。

3 2
1 3
2 8
4 6

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

1 1
306

0

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

102