問題文

$A \\cap B = \\emptyset$ を満たす $2$ つの整数の集合 $A, B$ に対して、$f(A,B)$ を以下のように定義します。

• $A \\cup B$ に含まれる要素を昇順に並べた数列を $C=(C_1,C_2,\\dots,C_{|A|+|B|})$ とする。
• $A=\\lbrace C_{k_1},C_{k_2},\\dots,C_{k_{|A|}}\\rbrace$ となるような $k_1,k_2,\\dots,k_{|A|}$ をとる。 このとき、$\\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$ です。

それぞれが $M$ 個の要素からなる $N$ 個の整数の集合 $S_1,S_2\\dots,S_N$ があり、各 $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)$ を求めてください。

制約

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